Problem:


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 r_1,r_2,..,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^9

1≤K≤10^5

1≤r_1<r_2< .. <r_K≤10^9

1≤Q≤10^5

0≤t_1<t_2< .. <t_Q≤10^9

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_1 r_2 .. r_K
Q
t_1 a_1
t_2 a_2
:
t_Q a_Q

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



Sample input:
180
3
60 120 180
3
30 90
61 1
180 180


Sample output:
60
1
120

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc082/tasks/arc082_d

aiが固定ならば、ただクエリをソートしてシミュレーションしながら答えを出せばよい
今回はそうでないので、方法を考える

一度でも砂が落ち切ってしまえば、その後はaiに関わらず、答えは等しくなる
おちきっていない場合、常に砂が移動し続けるので、初期値からの差分が常に等しくなる
よって、落ち切らないaの範囲を保持し、一度も落ち切らない場合の初期からの差分
& 落ち切ってしまった場合のシミュレーション結果を用いて答えればよい

→どのタイミング(区間)で落ち切るかでその後の動きが違くね？？？
→死

→aの区間は高々3つに分けられる
→ aが少なく、a=0と同じに収束する場合、 aが大きく、a=Xと同じに収束する場合。、一度も落ち切らない場合
→そして、a=0,a=Xと同じになる場合は、それぞれaの初期値の区間の両端から侵食していく
→よって、a=0のシミュ、a=Xのシミュ、落ち切らない差分シミュ。その時あるaがどれに属すかの区間
を用いてシミュレーションしながらdp的に処理してあげればよい

あとは実装が面倒そう
"""
from collections import deque
X = int(input())
K = int(input())

r = list(map(int,input().split()))
#番兵
r.append(float("inf"))
r.append(0)

ta = deque([])
Q = int(input())

for i in range(Q):
    t,a = map(int,input().split())
    ta.append([t,a])

ZA = 0 #初期がa=0の時のシミュ結果
XA = X #初期がXの時
D  = 0 #差分計算
Zmax = 0 #aがZmax以下ならZAと等しくなる
Xmin = X #aがXmin以上ならXAと等しくなる

for i in range(K+1):

    time = r[i] - r[i-1]

    #クエリの処理(r[i]以下に関して)
    if i % 2 == 0: #Aが減っていく
        
        while len(ta) > 0 and ta[0][0] <= r[i]:
            t,a = ta.popleft()
            td = t - r[i-1]

            if a <= Zmax:
                print (max( 0 , ZA-td ))
            elif a >= Xmin:
                print (max (0 , XA-td ))
            else:
                print (max (0 , a+D-td))

        D -= time
        Zmax = max(Zmax,-1*D)
        ZA = max(0,ZA-time)
        XA = max(0,XA-time)

    else: #Aが増えていく
        
        while len(ta) > 0 and ta[0][0] <= r[i]:
            t,a = ta.popleft()
            td = t - r[i-1]

            if a <= Zmax:
                print (min( X , ZA+td ))
            elif a >= Xmin:
                print (min (X , XA+td ))
            else:
                print (min (X , a+D+td))

        D += time
        Xmin = min(Xmin,X-D)
        ZA = min(X,ZA+time)
        XA = min(X,XA+time)

Submission status: Accepted

Solution code:
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

    X = int(input())
    K = int(input())
    R = list(map(int, input().split()))
    Q = []
    for r in R:
        Q.append((r, -1))
    q = int(input())
    for _ in range(q):
        t, a = map(int, input().split())
        Q.append((t, a))
    Q.sort(key=itemgetter(0))

    #print(Q)
    prev = 0
    m = 0
    M = X
    flg = -1
    R_cs = 0
    for t, a in Q:
        if a < 0:
            r = t - prev
            R_cs -= r * flg
            if flg == -1:
                m = max(0, m-r)
                M = max(0, M-r)
                flg = 1
            else:
                m = min(X, m+r)
                M = min(X, M+r)
                flg = -1
            prev = t
        else:
            if m == M:
                if flg == 1:
                    print(min(X, m + t - prev))
                else:
                    print(max(0, m - t + prev))
            else:
                am = m + R_cs
                aM = M + R_cs
                #print('am', am, 'aM', aM, m, M)
                if a <= am:
                    if flg == 1:
                        print(min(X, m + t - prev))
                    else:
                        print(max(0, m - t + prev))
                elif a >= aM:
                    if flg == 1:
                        print(min(X, M + t - prev))
                    else:
                        print(max(0, M - t + prev))
                else:
                    if flg == 1:
                        print(min(X, m + (a - am) + t - prev))
                    else:
                        print(max(0, m + (a - am) - t + prev))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    x = int(input())
    k = int(input())
    rr = LI()
    q = int(input())
    ta = LLI(q)
    # [時間,命令,(a)]でタイムラインに登録
    # 命令0でひっくり返す 1で質問に答える
    timeline = []
    for r in rr:
        heappush(timeline, [r, 0, 0])
    for t, a in ta:
        heappush(timeline, [t, 1, a])
    # print(timeline)
    # Aのパーツが一度でも空や満タンになると、aは関係なくなるのが大事な所
    # だから空になるaはal未満のaとしてひとまとめ
    # 満タンになるaはarより大きいaとして
    # ひとまとめで管理する
    #       l       r
    # a=0 1 2 3 4 5 6 7 8 9 10...
    #       al      ar
    # al(=2)未満のaの砂の量sl
    # ar(=6)より大きいaの砂の量sr
    # al以上ar以下のaの砂の量a+sm
    sl = sm = 0
    sr = x
    al = 0
    ar = x
    rev_t = 0
    trend = False
    while timeline:
        t, op, a = heappop(timeline)
        sd = t - rev_t
        if op:
            if trend:
                if a < al:
                    print(min(sl + sd, x))
                elif a > ar:
                    print(min(sr + sd, x))
                else:
                    print(min(a + sm + sd, x))
            else:
                if a < al:
                    print(max(sl - sd, 0))
                elif a > ar:
                    print(max(sr - sd, 0))
                else:
                    print(max(a + sm - sd, 0))
        else:
            if trend:
                sl = min(sl + sd, x)
                sr = min(sr + sd, x)
                ar = min(ar, x - sm - sd - 1)
                sm += sd
            else:
                sl = max(sl - sd, 0)
                sr = max(sr - sd, 0)
                al = max(al, sd - sm + 1)
                sm -= sd
            trend = not trend
            rev_t = t
        # print(t, op, a, al, ar, sl, sm, sr)
main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect
def input():
	return sys.stdin.readline()[:-1]

x = int(input())
k = int(input())
z = [0] + list(map(int, input().split()))
s = [z[i+1] - z[i] for i in range(k)]

lr = [[0, x]]
pq = [[0, x]]

for i in range(k):
	l, r = lr[-1]
	p, q = pq[-1]
	if i%2 == 0:
		lr.append([max(l-s[i], 0), max(r-s[i], 0)])
		pq.append([min(p + max(min(s[i], x)-l, 0), q), q])
	else:
		lr.append([min(l+s[i], x), min(r+s[i], x)])
		pq.append([p, max(q - max(r-max(x-s[i], 0), 0), p)])

q = int(input())
for _ in range(q):
	t, a = map(int, input().split())
	i = bisect(z, t) - 1
	t -= z[i]
	if a <= pq[i][0]:
		y = lr[i][0]
	elif a >= pq[i][1]:
		y = lr[i][1]
	else:
		y = lr[i][0] + a - pq[i][0]

	if i%2 == 0:
		print(max(y-t, 0))
	else:
		print(min(y+t, x))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

"""
X定数だった。両極端な場合が合流する。
[0,L]上定数A、[R,X]上定数B、その間は線形
"""

X = int(input())
K = int(input())
R = [int(x) for x in input().split()]
Q = int(input())
TA = [tuple(int(x) for x in input().split()) for _ in range(Q)]

task = sorted([(r,-1) for r in R] + [(t,a) for t,a in TA])

L = 0
R = X
A = 0
B = X
dx = -1 # 初めは減る方
current = 0
answer = []
for t,a in task:
    # とりあえず上限を突破して落とす
    A += dx * (t-current)
    B += dx * (t-current)
    current = t
    if a != -1:
        # 体積の計算
        if a <= L:
            x = A
        elif a >= R:
            x = B
        else:
            x = A+(B-A)//(R-L)*(a-L)
        if x < 0:
            x = 0
        if x > X:
            x = X
        answer.append(x)
    else:
        dx = -dx
        if A < B:
            if A < 0:
                L += (-A)
                A = 0
            if B > X:
                R -= (B-X)
                B = X
            if A > X:
                A = X
                B = X
                L = 0
                R = 0
            if B < 0:
                A = 0
                B = 0
                L = 0
                R = 0
        elif A >= B:
            if A > X:
                L += (A-X)
                A = X
            if B < 0:
                R -= (-B)
                B = 0
            if A < 0:
                A = 0
                B = 0
                L = 0
                R = 0
            if B > X:
                A = X
                B = X
                L = 0
                R = 0
        if R < L:
            R = L

print(*answer,sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect

def main():
    X = int(input())
    K = int(input())
    r = list(map(int, input().split()))
    Q = int(input())
    q_list = []
    for i in range(Q):
        q_list.append(list(map(int, input().split())))

    r = [0] + r
    a = [0]
    upper_limit = [X]
    lower_limit = [0]

    x, ux, lx = 0, X, 0
    for i in range(1, K + 1):
        diff = r[i] - r[i - 1]
        if i % 2 == 1:
            x -= diff
            ux -= diff
            ux = max(ux, 0)
            lx -= diff
            lx = max(lx, 0)
        else:
            x += diff
            ux += diff
            ux = min(ux, X)
            lx += diff
            lx = min(lx, X)
        a.append(x)
        upper_limit.append(ux)
        lower_limit.append(lx)

    asc_i = [0]
    dsc_i = [1]
    x = 0
    for i in range(2, K + 1, 2):
        if x < a[i]:
            x = a[i]
            asc_i.append(i)
    x = a[1]
    for i in range(3, K + 1, 2):
        if a[i] < x:
            x = a[i]
            dsc_i.append(i)

    asc_a = [a[i] for i in asc_i]
    dsc_a = [-a[i] for i in dsc_i]


    for [t, a0] in q_list:
        ri = bisect.bisect_right(r, t) - 1

        ui = bisect.bisect_left(asc_a, X - a0)
        li = bisect.bisect_left(dsc_a, a0)

        ai, di = None, None
        if ui < len(asc_i):
            ai = asc_i[ui]
            if ri < ai:
                ai = None
        if li < len(dsc_i):
            di = dsc_i[li]
            if ri < di:
                di = None

        d = 0
        if (not ai is None) or (not di is None):
            if ai is None:
                d = -1
            elif di is None:
                d = 1
            else:
                d = 1 if ai < di else -1

        x = a0 + a[ri]
        if d == 1:
            x = upper_limit[ri]
        elif d == -1:
            x = lower_limit[ri]
        x += (t - r[ri]) * (-1 if ri % 2 == 0 else 1)
        x = min(max(x, 0), X)

        print(x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect
X=int(input())
K=int(input())
rs=[0]
for r in input().split():
  rs.append(int(r))
A=[[(0,0),(X,X)]]
min_sup=0
max_inf=X
pre_r=0
for i,r in enumerate(rs[1:]):
  d=r-pre_r
  pre_r=r
  m,M=A[-1][0][0],A[-1][1][0]
  if i%2==0:
    if m-d>=0:
      new_m=m-d
    else:
      new_m=0
      min_sup=min_sup+d-m
    if M-d>0:
      new_M=M-d
    else:
      new_M=0
      max_inf=0
  else:
    if M+d<=X:
      new_M=M+d
    else:
      new_M=X
      max_inf=max_inf-(d-(X-M))
    if m+d<X:
      new_m=m+d
    else:
      new_m=X
      min_sup=X
  if new_m==new_M:
    min_sup=X
    max_inf=0             
  A.append([(new_m,min_sup),(new_M,max_inf)])
Q=int(input())
for q in range(Q):
  t,a=map(int,input().split())
  r_num=bisect(rs,t)-1
  m,min_sup=A[r_num][0]
  M,max_inf=A[r_num][1]
  r=rs[r_num]
  if r_num%2==0:
    if a<=min_sup:
      print(max(m-(t-r),0))
    elif min_sup<a<max_inf:
      print(max(m+(a-min_sup)-(t-r),0))
    else:
      print(max(M-(t-r),0))
  else:
    if a<=min_sup:
      print(min(m+(t-r),X))
    elif min_sup<a<max_inf:
      print(min(m+(a-min_sup)+(t-r),X))
    else:
      print(min(M+(t-r),X))

Submission status: Accepted

Solution code:
input = __import__('sys').stdin.readline
MIS = lambda: map(int,input().split())
 
# f(a) = z                 a <= x1
#        a+z-x1      x1 <= a <= x2
#        x2+z-x1     x2 <= a
class Sandgraph:
    def __init__(_, X):
        _.z = _.x1 = 0
        _.x2 = X
    
    def add(_, dt):
        # Go towards the ceiling
        d1 = min(dt, X-(_.x2+_.z-_.x1))
        _.z+= d1
        dt-= d1
        # Reduce the diagonal
        d1 = min(dt, _.x2-_.x1)
        _.z+= d1
        _.x2-= d1
    
    def sub(_, dt):
        # Go towards the floor
        d1 = min(dt, _.z)
        _.z-= d1
        dt-= d1
        # Reduce the diagonal
        d1 = min(dt, _.x2-_.x1)
        _.x1+= d1
    
    def __call__(_, a):
        if a <= _.x1: return _.z
        elif a <= _.x2: return a + _.z - _.x1
        else: return _.x2 + _.z - _.x1
 
X = int(input())
k = int(input())
rev = list(MIS())
Q = int(input())
sand = Sandgraph(X)
 
last_t = 0
i = 0 # even -, odd +
for QUERY in range(Q):
    t, a = MIS()
    while i<k and rev[i] <= t:
        dt = rev[i] - last_t
        if i%2 == 0: sand.sub(dt)
        else: sand.add(dt)
        last_t = rev[i]
        i+= 1
    dt = t - last_t
    if i%2 == 0: sand.sub(dt)
    else: sand.add(dt)
    print(sand(a))
    last_t = t

Submission status: Accepted

Solution code:
import bisect
def inpl(): return [int(i) for i in input().split()]

X = int(input())
K = int(input())
r = [0] + inpl()
stu = [()]*(K+1)
stu[0] = (X, 0, 0)
for i, v in enumerate(r[1:], 1):
    s, t, u = stu[i-1]
    if i%2:
        rs = r[i-1] - r[i]
        ap = - rs - t
        if ap >= s:
            stu[i] = 0, 0, 0
        elif ap >= u:
            stu[i] = s, t+rs, ap
        else:
            stu[i] = s, t+rs, u
    else:
        rs = r[i] - r[i-1]
        ap = X - rs - t
        if ap >= s:
            stu[i] = s, t+rs, u
        elif ap >= u:
            stu[i] = ap, t+rs, u
        else:
            stu[i] = X, 0, X
Q = int(input())
for _ in range(Q):
    ti, a = inpl()
    x = bisect.bisect_right(r, ti)
    ti -= r[x-1]
    s, t, u = stu[x-1]
    if a >= s:
        R = s + t
    elif a >= u:
        R = a + t
    else:
        R = u + t
    if x % 2:
        print(max(0, R - ti))
    else:
        print(min(X, R + ti))

Submission status: Accepted

Solution code:
X = int(input())
K = int(input())
R = list(map(int, input().split()))
Q = int(input())


ami = [0]*(K+1)
ama = [X] + [0]*K
cusummi = [0]*(K+1)
cusumma = [0]*(K+1)
cusum = [0]*(K+1)
pr = 0
for i, r in enumerate(R):
    d = pr-r if i%2==0 else r-pr
    cusum[i+1] = cusum[i] + d
    cusummi[i+1] = min(cusummi[i], cusum[i+1])
    cusumma[i+1] = max(cusumma[i], cusum[i+1])
    ami[i+1] = min(max(ami[i] + d, 0), X)
    ama[i+1] = min(max(ama[i] + d, 0), X)
    pr = r

import bisect
for _ in range(Q):
    t, a = map(int, input().split())
    i = bisect.bisect_right(R, t)
    t1 = R[i-1] if i!=0 else 0
    t2 = t-t1
    d = -t2 if i%2==0 else t2
    if ama[i]==ami[i]:
        print(min(max(ama[i] + d, 0), X))
        continue
    ans = a+cusum[i]
    if -cusummi[i]>a:
        ans += -cusummi[i]-a
    if cusumma[i]>(X-a):
        ans -= cusumma[i]-(X-a)
    print(min(max(ans+d, 0), X))

Submission status: Accepted

Solution code:
X = int(input())
K = int(input())
rs = list(map(int,input().split()))
Q = int(input())
qs = [tuple(map(int,input().split())) for i in range(Q)]

dx = -1
ri = 0
offset = 0
upper,lower = X,0
prev_r = 0
ans = []
for t,a in qs:
    while ri < len(rs) and rs[ri] <= t:
        tmp_offset = dx * (rs[ri] - prev_r)
        if dx == 1:
            upper = min(X, upper + tmp_offset)
            lower = min(X, lower + tmp_offset)
        else:
            upper = max(0, upper + tmp_offset)
            lower = max(0, lower + tmp_offset)
        offset += tmp_offset
        dx *= -1
        prev_r = rs[ri]
        ri += 1
    a = max(lower, min(upper, a+offset))
    dt = t - prev_r
    a = max(0, min(X, a + dx*dt))
    ans.append(a)

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
X = int(input())
K = int(input())
r_lst = [int(_) for _ in input().split()]
Q = int(input())
t_lst, a_lst = [], []
for i in range(Q):
    buf = input().split()
    t_lst.append(int(buf[0]))
    a_lst.append(int(buf[1]))
    
pos_lst = []
for i, r in enumerate(r_lst):
    direc = "+" if i%2==0 else "-"
    pos_lst.append((r, direc))
for i, t in enumerate(t_lst):
    pos_lst.append((t, i))
pos_lst = sorted(pos_lst, key=lambda tup: tup[0])


left, right  = 0, X
val = [0, 0, X] 

direc = "-"
prv = 0
for pos in pos_lst:
#    print(left, right)
#    print(val)
#    print(pos)
#    print()
    
    elapsed = pos[0] - prv
    prv = pos[0]
    
    if direc == "+":
        val[0] = min(X, val[0] + elapsed)
        val[1] += elapsed
        val[2] = min(X, val[2] + elapsed)
        right = min(right, X - val[1])
    else:
        val[0] = max(0, val[0] - elapsed)
        val[1] -= elapsed
        val[2] = max(0, val[2] - elapsed)     
        left = max(left, -(val[1]))
        
    if pos[1] == "+" or pos[1] == "-":
        direc = pos[1]
    else: #is query
        a = a_lst[pos[1]]
        
        if a <= left:
            print(val[0])
        elif a >= right:
            print(val[2])
        else:
            print( a + val[1])

Submission status: Accepted

Solution code:
X = int(input())
K = int(input())
R = [int(x) for x in reversed(input().split())]
for i in range(0,K-1): R[i] -= R[i+1]
Q = int(input())

aM = X
M = X
am = 0
m = 0
now = 0
sign = -1
timer = R.pop()

def Go(time):
    global aM,M,am,m
    if sign==1:
        if m+time>X:
            m = X
            M = X
            aM = am
        elif M+time>X:
            m += time
            M = X
            aM = am + M - m
        else:
            m += time
            M += time
    else:
        if M-time<0:
            m = 0
            M = 0
            am = aM
        elif m-time<0:
            m = 0
            M -= time
            am = aM + m - M
        else:
            m -= time
            M -= time

for i in range(Q):
    t,a = [int(x) for x in input().split()]
    t -= now
    now += t
    
    while t>=timer:
        Go(timer)
        t -= timer
        if R:
            timer = R.pop()
        else:
            timer = float("inf")
        sign *= -1
    
    Go(t)
    timer -= t
    
    if a<am:
        print(m)
    elif a>aM:
        print(M)
    else:
        print(m+a-am)

Submission status: Accepted

Solution code:
def calc_ans(x):
    if x < 0:
        return 0
    elif x < X:
        return x
    else:
        return X


if __name__ == '__main__':
    # 砂の合計量
    X = int(input())

    # ひっくり返す回数
    K = int(input())
    # ひっくり返す秒数
    r = list(map(int, input().split()))
    # クエリの個数
    Q = int(input())

    # r の制御のための変数
    j = 0
    sign = -1
    s = 0
    e = X
    y = 0
    sand_quantity = [r[0]]
    for i in range(1, K):
        sand_quantity.append(r[i] - r[i - 1])

    chasm_time = 0
    for i in range(Q):
        # t:時刻 a:初期に A に入っている砂の量
        t, a = list(map(int, input().split()))
        while j < K and r[j] < t:
            y += sign * sand_quantity[j]
            # sについて更新
            if y < 0:
                s += -y
                if e < s:
                    s = e
                y = 0
            # eについて更新
            if X < y + e - s:
                tmp_diff = (y + e - s) - X
                e -= tmp_diff
                if e < s:
                    e = s
            if X < y:
                y = X

            chasm_time = r[j]
            j += 1
            sign *= -1

        tmp_time = t - chasm_time

        if a < s:
            ret = y
        elif a < e:
            ret = y + a - s
        else:
            ret = y + e - s

        ret += tmp_time * sign

        print(calc_ans(ret))
        # print("s:" + str(s) + " e:" + str(e) + " y:" + str(y) + " a:" + str(a) + " ret:" + str(ret))

Submission status: Accepted

Solution code:
ri = lambda: map(int, raw_input().split())

x = input()
k, r = input(), ri()

j, v, lb, rb, pt = 0, 0, 0, x, 0
L, R = 0, x
for i in xrange(input()):
    t, a = ri()
    while j < k and r[j] <= t:
        d = r[j] - pt
        pt = r[j]
        if j % 2 == 0:
            v -= d
            lb = max(lb - d, 0)
            rb = max(rb - d, 0)
        else:
            v += d
            lb = min(lb + d, x)
            rb = min(rb + d, x)
        L = max(L, -v)
        R = min(R, x - v)
        j += 1
    ans = 0
    if L <= a <= R:
        ans = a + v
    else:
        ans = lb if a < L else rb
    if j % 2 == 0:
        ans = max(ans - (t - pt), 0)
    else:
        ans = min(ans + (t - pt), x)
    print ans

Submission status: Accepted

Solution code:
import bisect
oX = int(input())
K = int(input())
r= list(map(int,input().split()))

# a X-a
# min(max(0,a-r[0]))
#  a-r[0]+r[1]

def calc_time(t):
    val = bisect.bisect_left(t,r)
    diff= t- r[val]
    return val,diff


# [sep1,sep2,a<sep1,sep1<a<sep2,a>sep2  ]

last =(0,oX,0 ,0,oX)
res =[last]
for i,tr in enumerate(r):
    sep1,sep2,X,Y,Z=last
    dt = tr if i==0 else tr-r[i-1]
    if i%2==0: # a ->b

        X = max(0,X-dt)
        Y = Y-dt
        Z = max(0,Z-dt)
        sep1 = max(sep1,-Y)
    else: #b-> a
        X = min(oX,X+dt)
        Y= Y+dt

        Z = min(oX,Z+dt)
        sep2 = min(sep2,oX-Y)

    last = (sep1,sep2,X,Y,Z)
    res.append(last)

#print(res)


Q = int(input())

r_index=0
r.insert(0,0)
r.append(10000000000)
for i in range(Q):
    def calc(X,r_index,diff):
        tmp = 1 if r_index%2 else -1
        return min(oX,max(0,X +tmp* diff))
    t,a =list(map(int,input().split()))
    while r[r_index]< t:
        if r[r_index+1] >t:
            break
        r_index+=1
    sep1, sep2, X, Y, Z = res[r_index]
    diff = t -r[r_index]
    #print(t,diff,r_index,r[r_index])
    if a< sep1:
        print(calc(X,r_index,diff))
    elif a>sep2:
        print(calc(Z,r_index,diff))
    else:
        print(calc(a+Y,r_index,diff))

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open('f1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    X = read_int()
    K = read_int()
    r = read_int_list()
    Q = read_int()
    j = 0
    sign = -1
    s = 0
    e = X
    y = 0
    origin = 0
    out = [0] * Q
    for i in range(Q):
        t, a = read_int_list()
        while j < K and r[j] < t:
            d = r[j] - origin
            y += d * sign
            if y < 0:
                s += abs(y)
                if s > e:
                    s = e
                y = 0
            if y + e - s > X:
                diff = (y + e - s) - X
                e -= diff
                if e < s:
                    e = s
            if y > X:
                y = X
            origin = r[j]
            j += 1
            sign *= -1
        d = t - origin
        if a <= s:
            res = y
        elif a <= e:
            res = y + a - s
        else:
            res = y + e - s
        res += d * sign
        if res < 0:
            res = 0
        if res > X:
            res = X
        out[i] = res
    return out


def main():
    res = solve()
    print(*res, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# F
# input
from bisect import bisect
X = int(input())
K = int(input())
r_list = [0] + list(map(int, input().split()))

Q = int(input())
query_list = [list(map(int, input().split())) for _ in range(Q)]


MmRL_list = []

# M:max, m:min, R:min_a(M), L:max_a(m)
M = X
m = 0
R = X
L = 0

MmRL_list.append([M, m, R, L])

for i in range(K):
    M_ = M
    m_ = m
    R_ = R
    L_ = L
    lag = r_list[i+1] - r_list[i]
    # update
    if i % 2 == 0:
        if M_ - lag < 0:
            M = 0
            R = 0
        else:
            M = M_ - lag
            R = R_
        if m_ - lag < 0:
            m = 0
            L = L_ + lag - m_
        else:
            m = m_ - lag
            L = L_
    else:
        if M_ + lag > X:
            M = X
            R = R_ - (M_ + lag - X)
        else:
            M = M_ + lag
            R = R_
        if m_ + lag > X:
            m = X
            L = X
        else:
            m = m_ + lag
            L = L_
    MmRL_list.append([M, m, R, L])
        

# print(MmRL_list)
for q in range(Q):
    t, a = query_list[q]
    j = bisect(r_list, t) - 1
    # find status then
    M, m, R, L = MmRL_list[j]
    if a <= L:
        a_ = m
    elif a >= R:
        a_ = M
    else:
        a_ = m + (a - L)
    t_ = t - r_list[j]
    if j % 2 == 0:
        res = max(a_ - t_, 0)
    else:
        res = min(a_ + t_, X)
    print(res)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    x = I()
    k = I()
    r = LI()
    q = I()
    t = [LI() for _ in range(q)]
    a = [[0,0,0,x,0,0]]
    d = 0
    for i in range(k):
        c = a[-1][:]
        rr = r[i] - d
        d = r[i]
        if i % 2 == 0:
            c[1] -= rr
            c[3] -= rr
            c[4] -= rr
            if c[0] > c[1]:
                c[0] = c[1]
        else:
            c[1] += rr
            c[3] += rr
            c[4] += rr
            if c[2] < c[1]:
                c[2] = c[1]
        if c[3] > x:
            c[3] = x
        if c[3] < 0:
            c[3] = 0
        if c[4] > x:
            c[4] = x
        if c[4] < 0:
            c[4] = 0

        c[5] = r[i]

        a.append(c)
    def bs(i):
        ma = k
        mi = 0
        mm = 0
        while ma > mi and (ma+mi) // 2 != mm:
            mm = (ma+mi) // 2
            if a[mm][5] < i:
                mi = mm
            else:
                ma = mm - 1
        if a[mm][5] > i:
            return mm-1
        if mm == k:
            return k
        if a[mm+1][5] <= i:
            return mm+1
        return mm

    #print(a)
    rr = []
    for c,d in t:
        ti = bs(c)
        ai = a[ti]
        e = x-d
        #print(c,d,e,ti,ai)
        if d + ai[0] <= 0:
            tt = ai[4]
        elif e - ai[2] <= 0:
            tt = ai[3]
        else:
            tt = d + ai[1]
        #print('tt',tt)
        if ti % 2 == 0:
            tt -= c - ai[5]
        else:
            tt += c - ai[5]
        #print('tt2',tt)
        if tt < 0:
            tt = 0
        elif tt > x:
            tt = x
        rr.append(tt)

    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
input = __import__('sys').stdin.readline
MIS = lambda: map(int,input().split())

# f(a) = z                 a <= x1
#        a+z-x1      x1 <= a <= x2
#        x2+z-x1     x2 <= a
class Sandgraph:
    def __init__(_, X):
        _.z = _.x1 = 0
        _.x2 = X
    
    def __repr__(_):
        return f"<{_.z} {_.x1} {_.x2}>"
    
    def add(_, dt):
        # Go towards the ceiling
        d1 = min(dt, X-(_.x2+_.z-_.x1))
        _.z+= d1
        dt-= d1
        # Reduce the diagonal
        d1 = min(dt, _.x2-_.x1)
        _.z+= d1
        _.x2-= d1
    
    def sub(_, dt):
        # Go towards the floor
        d1 = min(dt, _.z)
        _.z-= d1
        dt-= d1
        # Reduce the diagonal
        d1 = min(dt, _.x2-_.x1)
        _.x1+= d1
    
    def __call__(_, a):
        if a <= _.x1: return _.z
        elif a <= _.x2: return a + _.z - _.x1
        else: return _.x2 + _.z - _.x1

X = int(input())
k = int(input())
rev = list(MIS())
Q = int(input())
sand = Sandgraph(X)

last_t = 0
i = 0 # even -, odd +
for QUERY in range(Q):
    t, a = MIS()
    while i<k and rev[i] <= t:
        dt = rev[i] - last_t
        if i%2 == 0: sand.sub(dt)
        else: sand.add(dt)
        last_t = rev[i]
        i+= 1
    dt = t - last_t
    if i%2 == 0: sand.sub(dt)
    else: sand.add(dt)
    print(sand(a))
    last_t = t