Sandglass

时间限制: 1 Sec 内存限制: 128 MB 

原题链接 

题目描述

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

样例输入

180 

3 

60 120 180 

3 

30 90 

61 1 

180 180

样例输出

60 

1 

120

题解

我的做法是进行带优化的模拟，因为题目输入是确保后一个时间一定大于前一个时间的，所以对于翻转的模拟总共只需要按顺序进行一次便可，最后使用数学结论根据时间和初始质量推出答案。 

需要特别注意的是，这道题会卡输入输出，如果不使用scanf/printf的话，必须要关闭同步锁且不能使用endl，不然会TLE。（可能是华东OJ的原因）

心疼那将近一半被输入输出卡掉的提交QAQ

代码

42 ms/1664 KB（AtCoder） 

80 ms/2080 KB（华东 OJ）

#include 
      
       #include 
       
        using namespace std;int x, k, q, t, a, low, up, add, delta, now, ans, r[100007];bool flag;int cal(int tt, int lower = 0, int upper = x) {    if (tt < lower) return lower;    if (tt > upper) return upper;    return tt;}int main() {    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);    cin >> x >> k;    for (int i = 1; i <= k; i++) cin >> r[i];    cin >> q;    low = x, now = 1;    while (q--) {        cin >> t >> a;        while (t >= r[now] && now <= k) {            delta = (flag ? 1 : -1) * (r[now] - r[now - 1]), add += delta;            up = cal(delta + up), low = cal(delta + low);            flag = !flag, now++;        }        ans = cal((flag ? 1 : -1) * (t - r[now - 1]) + cal(a + add, up, low));        cout << ans << '\n';    }    return 0;}