AtCoder Regular Contest 082-F-Sandglass

F - Sandglass

Time limit : 2sec / Memory limit : 256MB

Score : 700 points

Problem Statement
We have a sandglass consisting of two bulbs, bulb A and bulb B. These bulbs contain some amount of sand. When we put the sandglass, either bulb A or B lies on top of the other and becomes the upper bulb. The other bulb becomes the lower bulb.

The sand drops from the upper bulb to the lower bulb at a rate of 1 gram per second. When the upper bulb no longer contains any sand, nothing happens.

Initially at time 0, bulb A is the upper bulb and contains a grams of sand; bulb B contains X−a grams of sand (for a total of X grams).

We will turn over the sandglass at time r1,r2,..,rK. Assume that this is an instantaneous action and takes no time. Here, time t refer to the time t seconds after time 0.

You are given Q queries. Each query is in the form of (ti,ai). For each query, assume that a=ai and find the amount of sand that would be contained in bulb A at time ti.

Constraints
1≤X≤109
1≤K≤105
1≤r1< r2< ..< rK≤109
1≤Q≤105
0≤t1< t2< ..< tQ≤109
0≤ai≤X(1≤i≤Q)
All input values are integers.
Input
The input is given from Standard Input in the following format:

X
K
r1 r2 .. rK
Q
t1 a1
t2 a2
:
tQ aQ
Output
For each query, print the answer in its own line.

Sample Input 1
180
3
60 120 180
3
30 90
61 1
180 180
Sample Output 1
60
1
120
In the first query, 30 out of the initial 90 grams of sand will drop from bulb A, resulting in 60 grams. In the second query, the initial 1 gram of sand will drop from bulb A, and nothing will happen for the next 59 seconds. Then, we will turn over the sandglass, and 1 second after this, bulb A contains 1 gram of sand at the time in question.

Sample Input 2
100
1
100000
4
0 100
90 100
100 100
101 100
Sample Output 2
100
10
0
0
In every query, the upper bulb initially contains 100 grams, and the question in time comes before we turn over the sandglass.

Sample Input 3
100
5
48 141 231 314 425
7
0 19
50 98
143 30
231 55
342 0
365 100
600 10
Sample Output 3
19
52
91
10
58
42
100

题目大意：有一个沙漏，沙子总量为$x$，初始情况上A下B，给出翻转时刻和多个询问，每个询问有询问时间和初始A中沙子量，求出询问时刻A中的沙子量。
解题思路：维护间断点，使值域在$[0,x]$之间。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <cstdlib>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+5;
int t[MAXN],m[MAXN];

int main()
{
    int x,n;
    while(scanf("%d%d",&x,&n)!=EOF)
    {
        vector<PII> events;
        int tmp;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&tmp);
            events.emplace_back(tmp,-1);
        }
        int q; scanf("%d",&q);
        for(int i=0;i<q;i++)
        {
            scanf("%d%d",&t[i],&m[i]);
            events.emplace_back(t[i],i);
        }
        sort(events.begin(),events.end());
        int dir=-1,a=0,ya=0,b=x,yb=x,t0=0;
        for(auto event:events)
        {
            int t=event.first;
            if(t0<t)
            {
                int dt=t-t0;
                if(dir==-1)
                {
                    if(ya>=dt)
                    {
                        ya-=dt;
                        yb-=dt;
                    }else if(yb<dt)
                    {
                        a=ya=b=yb=0;
                    }else
                    {
                        a+=dt-ya;
                        ya=0;
                        yb-=dt;
                    }
                }else
                {
                    if(yb+dt<=x)
                    {
                        ya+=dt;
                        yb+=dt;
                    }else if(ya+dt>x)
                    {
                        a=b=0;
                        ya=yb=x;
                    }else
                    {
                        b-=(dt-x+yb);
                        yb=x;
                        ya+=dt;
                    }
                }
            }
            t0=t;
            int id=event.second;
            if(id!=-1)
            {
                if(m[id]<a) printf("%d\n",ya);
                else if(m[id]>b) printf("%d\n",yb);
                else printf("%d\n",ya+m[id]-a);
            }else
            {
                dir*=(-1);
            }
        }
    }
    return 0;
}