AtCoder Regular Contest 082 F

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 r₁,r₂,..,r_K. 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 (t_i,a_i). For each query, assume that a=a_i and find the amount of sand that would be contained in bulb A at time t_i.

Constraints

1≤X≤10⁹
1≤K≤10⁵
1≤r₁<r₂<..<r_K≤10⁹
1≤Q≤10⁵
0≤t₁<t₂<..<t_Q≤10⁹
0≤a_i≤X(1≤i≤Q)
All input values are integers.

Input

The input is given from Standard Input in the following format:

X
K
r₁ r₂ .. r_K
Q
t₁ a₁
t₂ a₂
:
t_Q a_Q

Output

For each query, print the answer in its own line.

Sample Input 1

Copy

Sample Output 1

Copy

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

Copy

Sample Output 2

Copy

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

Copy

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

Copy

19
52
91
10
58
42
100
———————————————————————————————
题目大意就是就是有一个排序好的数列，每次全部数+或-一个数，然后把<0的变成0，>X的变成X
这样我们可以算出每个询问在最后一次翻转后的状态 维护一个mn（初值为0）和一个mx（初值为沙子总数）
这样每次修改的时候我们算一下mn和mx的变换之后就可以得到所有的值在最后都是在mn'和mx之间
得到最后一次旋转后的值之后就可以直接算了 其实就是类似线段树的限制值的范围的那种操作以及区间+ -
只是这里不需要而已

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M=1e5+7;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int ans[M],T[M];
struct pos{int T,s;}e[M];
int x,k=1,n,m,sgn=-1;
void calc(LL &k){if(k<0) k=0; if(k>x) k=x;}
int main(){
    x=read();
    n=read(); for(int i=1;i<=n;i++) T[i]=read();
    m=read(); for(int i=1;i<=m;i++) e[i].T=read(),e[i].s=read();
    LL h=0,mx=x,mn=0;
    for(int i=1;i<=m;i++){
        while(k<=n&&T[k]<=e[i].T){
            LL v=(T[k]-T[k-1])*sgn;
            mx+=v; mn+=v; h+=v;
            calc(mx); calc(mn);
            k++;sgn*=-1; 
        }
        LL now=e[i].s+h,nowh=(e[i].T-T[k-1])*sgn;
        if(now<mn) now=mn;
        if(now>mx) now=mx;
        now+=nowh; calc(now);
        printf("%lld
",now);
    }
    return 0;
}

View Code