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: Wrong Answer

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: Wrong Answer

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
        elif A > B:
            if A > X:
                L += (A-X)
                A = X
            if B < 0:
                R -= (-B)
                B = 0
        if R < L:
            R = L

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

Submission status: Wrong Answer

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: Wrong Answer

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
  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: Wrong Answer

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

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

    # r の制御のための変数
    j = 0
    sign = -1
    '''
    ある時刻を切り取り、横軸を最初のAの砂の量、縦軸をその時の砂の量とする。
    s:傾き始め
    e:傾き終わり
    c:切片
    '''
    s = 0
    e = X
    c = 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:
            c += sign * sand_quantity[j]
            c = max(min(X, c), -X)
            # sについて更新
            if s < -c:
                s = -c
                if e < s:
                    s = e
            # eについて更新
            if X - c < e:
                e = X - c
                if e < s:
                    e = s
            chasm_time = r[j]
            j += 1
            sign *= -1

        tmp_time = t - chasm_time

        if a < s:
            print(max(min(s + c + tmp_time * sign, X), 0))
        elif a < e:
            print(max(min(a + c + tmp_time * sign, X), 0))
        else:
            print(max(min(e + c + tmp_time * sign, X), 0))

        # print("s:" + str(s) + " e:" + str(e) + " c:" + str(c) + " a:" + str(a))

Submission status: Wrong Answer

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

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

    # r の制御のための変数
    j = 0
    sign = -1
    '''
    ある時刻を切り取り、横軸を最初のAの砂の量、縦軸をその時の砂の量とする。
    s:傾き始め
    e:傾き終わり
    c:切片
    '''
    s = 0
    e = X
    c = 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:
            c += sign * sand_quantity[j]
            # sについて更新
            if s < -c:
                s = -c
            # eについて更新
            if X - c < e:
                if X - c < s:
                    e = s
                else:
                    e = X - c
            chasm_time = r[j]
            j += 1
            sign *= -1

        tmp_time = t - chasm_time

        if a < s:
            print(max(min(s + c + tmp_time * sign, X), 0))
        elif a < e:
            print(max(min(a + c + tmp_time * sign, X), 0))
        else:
            print(max(min(e + c + tmp_time * sign, X), 0))

            # print("a:" + str(a) + " b:" + str(b) + " c:" + str(c))

Submission status: Wrong Answer

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

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

    # r の制御のための変数
    j = 0
    sign = -1
    '''
    ある時刻を切り取り、横軸を最初のAの砂の量、縦軸をその時の砂の量とする。
    a:傾き始め
    b:傾き終わり
    c:切片
    '''
    a = 0
    b = X
    c = 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, ini_sand = list(map(int, input().split()))
        while j < K and r[j] < t:
            c += sign * sand_quantity[j]
            c = max(min(c, X), -X)
            # aについて更新
            if a < -c:
                a = -c
            # bについて更新
            if X - c < b:
                if X - c < a:
                    b = a
                else:
                    b = X - c
            chasm_time = r[j]
            j += 1
            sign *= -1

        tmp_time = t - chasm_time

        if ini_sand < a:
            print(max(min(a + c + tmp_time * sign, X), 0))
        elif ini_sand < b:
            print(max(min(ini_sand + c + tmp_time * sign, X), 0))
        else:
            print(max(min(b + c + tmp_time * sign, X), 0))

            # print("a:" + str(a) + " b:" + str(b) + " c:" + str(c))

Submission status: Wrong Answer

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

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

    # r の制御のための変数
    j = 0
    sign = -1
    '''
    ある時刻を切り取り、横軸を最初のAの砂の量、縦軸をその時の砂の量とする。
    a:傾き始め
    b:傾き終わり
    c:切片
    '''
    a = 0
    b = X
    c = 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, ini_sand = list(map(int, input().split()))
        while j < K and r[j] < t:
            c += sign * sand_quantity[j]
            c = max(min(c, X), -X)
            # aについて更新
            if a < -c:
                a = -c
            # bについて更新
            if X - c < b:
                b = X - c
            chasm_time = r[j]
            j += 1
            sign *= -1

        tmp_time = t - chasm_time

        if ini_sand < a:
            print(max(min(a + c + tmp_time * sign, X), 0))
        elif ini_sand < b:
            print(max(min(ini_sand + c + tmp_time * sign, X), 0))
        else:
            print(max(min(b + c + tmp_time * sign, X), 0))

            # print("a:" + str(a) + " b:" + str(b) + " c:" + str(c))

Submission status: Wrong Answer

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

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

    # r の制御のための変数
    j = 0
    sign = -1
    '''
    ある時刻を切り取り、横軸を最初のAの砂の量、縦軸をその時の砂の量とする。
    a:傾き始め
    b:傾き終わり
    c:切片
    '''
    a = 0
    b = X
    c = 0
    # 出入りする砂の量
    sand_quantity = [r[0]]
    for i in range(1, K):
        sand_quantity.append(r[i] - r[i - 1])

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

            j += 1
            sign *= -1

        if j == 0:
            tmp_time = t
        else:
            tmp_time = t - r[j - 1]

        if ini_sand < a:
            print(max(min(a + c + tmp_time * sign, X), 0))
        elif ini_sand < b:
            print(max(min(ini_sand + c + tmp_time * sign, X), 0))
        else:
            print(max(min(b + c + tmp_time * sign, X), 0))

            # print("a:" + str(a) + " b:" + str(b) + " c:" + str(c))

Submission status: Wrong Answer

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

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

    # r の制御のための変数
    j = 0
    sign = -1
    '''
    ある時刻を切り取り、横軸を最初のAの砂の量、縦軸をその時の砂の量とする。
    a:傾き始め
    b:傾き終わり
    c:切片
    '''
    a = 0
    b = X
    c = 0
    # 出入りする砂の量
    sand_quantity = [r[0]]
    for i in range(1, K):
        sand_quantity.append(r[i] - r[i - 1])

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

            if X - c < b:
                b = X - c

            j += 1
            sign *= -1

        if j == 0:
            tmp_time = t
        else:
            tmp_time = t - r[j - 1]

        if ini_sand < a:
            print(max(min(a + c + tmp_time * sign, X), 0))
        elif ini_sand < b:
            print(max(min(ini_sand + c + tmp_time * sign, X), 0))
        else:
            print(max(min(b + c + tmp_time * sign, X), 0))

            # print("a:" + str(a) + " b:" + str(b) + " c:" + str(c))

Submission status: Wrong Answer

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

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

j, v, lb, rb, pt = 0, 0, 0, 0, 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: Wrong Answer

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

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

j, v, lb, rb, pt = 0, 0, 0, 0, 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 R
    if j % 2 == 0:
        ans = max(ans - (t - pt), 0)
    else:
        ans = min(ans + (t - pt), x)
    print ans

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import bisect


def main():
    X = int(input())
    K = int(input())
    rs = tuple(map(int, input().split()))
    Q = int(input())

    D = [None] * K
    u, l, au, am, al = 0, 1, 2, 3, 4
    pr = None
    for i, r in enumerate(rs):
        d = [None] * 5
        if i == 0:
            d[u] = X
            d[l] = min(r, X)
            d[au] = max(X - r, 0)
            d[am] = max(-r, -X)
            d[al] = 0
        else:
            pd = D[i-1]
            td = r - pr
            if i % 2 == 0:      # A -> B
                al_l = pd[al] - td
                if al_l >= 0:
                    d[u] = pd[u]
                    d[l] = pd[l]
                    d[au] = pd[au] - td
                    d[am] = pd[am] - td
                    d[al] = al_l
                else:
                    d[l] = pd[l] - al_l
                    d[al] = 0
                    d[au] = max(pd[au] - td, 0)
                    d[am] = max(pd[am] - td, 0)
                    if d[au] == 0:
                        d[u] = d[l]
                    else:
                        d[u] = pd[u]
            else:               # B -> A
                au_u = pd[au] + td
                if au_u <= X:
                    d[u] = pd[u]
                    d[l] = pd[l]
                    d[au] = au_u
                    d[am] = pd[am] + td
                    d[al] = pd[al] + td
                else:
                    au_d = au_u - X
                    d[u] = pd[u] - au_d
                    d[au] = X
                    d[am] = min(pd[am] + td, X)
                    d[al] = min(pd[al] + td, X)
                    if d[al] == X:
                        d[l] = d[u]
                    else:
                        d[l] = pd[l]
        D[i] = d
        pr = r
    # print(D)

    init_d = [X, 0, X, 0, 0]
    for q in range(Q):
        t, a = map(int, input().split())
        p = bisect.bisect(rs, t)
        if p == 0:
            pt = 0
            d = init_d
        else:
            pt = rs[p-1]
            d = D[p-1]
        if a <= d[l]:
            ta = d[al]
        elif a >= d[u]:
            ta = d[au]
        else:
            ta = a + d[am]
        td = t - pt
        if p % 2 == 0:          # A -> B
            ta = max(ta - td, 0)
        else:
            ta = min(ta + td, X)
        print(ta)


main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import bisect


def main():
    X = int(input())
    K = int(input())
    rs = tuple(map(int, input().split()))
    Q = int(input())

    D = [None] * K
    u, l, au, am, al = 0, 1, 2, 3, 4
    pr = None
    for i, r in enumerate(rs):
        d = [None] * 5
        if i == 0:
            d[u] = X
            d[l] = r
            d[au] = X - r
            d[am] = -r
            d[al] = 0
        else:
            pd = D[i-1]
            td = r - pr
            if i % 2 == 0:      # A -> B
                al_l = pd[al] - td
                if al_l >= 0:
                    d[u] = pd[u]
                    d[l] = pd[l]
                    d[au] = pd[au] - td
                    d[am] = pd[am] - td
                    d[al] = al_l
                else:
                    d[l] = pd[l] - al_l
                    d[al] = 0
                    d[au] = max(pd[au] - td, 0)
                    d[am] = max(pd[am] - td, 0)
                    if d[au] == 0:
                        d[u] = d[l]
                    else:
                        d[u] = pd[u]
            else:               # B -> A
                au_u = pd[au] + td
                if au_u <= X:
                    d[u] = pd[u]
                    d[l] = pd[l]
                    d[au] = au_u
                    d[am] = pd[am] + td
                    d[al] = pd[al] + td
                else:
                    au_d = au_u - X
                    d[u] = pd[u] - au_d
                    d[au] = X
                    d[am] = min(pd[am] + td, X)
                    d[al] = min(pd[al] + td, X)
                    if d[al] == X:
                        d[l] = d[u]
                    else:
                        d[l] = pd[l]
        D[i] = d
        pr = r
    # print(D)

    init_d = [X, 0, X, 0, 0]
    for q in range(Q):
        t, a = map(int, input().split())
        p = bisect.bisect(rs, t)
        if p == 0:
            pt = 0
            d = init_d
        else:
            pt = rs[p-1]
            d = D[p-1]
        if a <= d[l]:
            ta = d[al]
        elif a >= d[u]:
            ta = d[au]
        else:
            ta = a + d[am]
        td = t - pt
        if p % 2 == 0:          # A -> B
            ta = max(ta - td, 0)
        else:
            ta = min(ta + td, X)
        print(ta)


main()

Submission status: Time Limit Exceeded

Solution code:
def read_data_f(filename='arc082-e.dat'):
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), filename)
        with codecs.open(file_path, 'r', 'utf-8') as f:
            for each in f:
                lines.append(each.rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        lines.append(input())
        lines.append(input())
        lines.append(input())
        Q = int(lines[3])
        for i in range(Q):
            lines.append(input())

    return lines

def remain(X, a, t, isUp):
    if(isUp):
        return max(0, a-t)
    else:
        return min(a+t, X)


def F_Sandglass():
  
    raw_data = read_data_f('arc082-f.dat')
    X = int(raw_data[0])
    K = int(raw_data[1])
    r = list(map(int, raw_data[2].split()))
    Q = int(raw_data[3])
    a = []
    t = []
    for i in range(Q):
        tt, aa = list(map(int, raw_data[i+4].split()))
        a.append(aa)
        t.append(tt)

    # print(r)
    # print(t)
    # print(a)

    for j in range(Q):
        A = {}
        time = 0
        i = 0
        A[time] = a[j]
        start_time = 0
        start_status = True
        isUp = True

        while (i < K) and (time < t[j]):
            temp = remain(X, A[time], r[i] - time, isUp)
            time = r[i]
            A[time] = temp
            isUp = not isUp

            if(r[i] < t[j]):
                start_time = r[i]
                start_status = isUp
            i += 1

        result = remain(X, A[start_time], t[j] - start_time, start_status)
        print(result)



F_Sandglass()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def II(): return int(input())
def ILI(): return list(map(int, input().split()))
 
 
def read():
    X = II()
    K = II()
    r = ILI()
    Q = II()
    queries = [ILI() for __ in range(Q)]
    return X, K, r, Q, queries
 
 
def solve(X, K, r, Q, queries):
    l_ans = []
    r.insert(0, 0)
    dif_r = [r[i + 1] - r[i] for i in range(K)]
    dif_r.append(10 ** 9)
    for query in queries:
        t, a = query
        dif_r_ind = 0
        now_state = 0
        now_time = 0
        ans = a
        while True:
            if now_time + dif_r[dif_r_ind] > t:
                if now_state == 1:
                    ans += t - now_time
                    ans = min(X, ans)
                else:
                    ans -= t - now_time
                    ans = max(0, ans)
                break
            else:
                if now_state == 1:
                    ans += dif_r[dif_r_ind]
                    ans = min(X, ans)
                else:
                    ans -= dif_r[dif_r_ind]
                    ans = max(0, ans)
                now_time += dif_r[dif_r_ind]
                now_state = (now_state + 1) % 2
                dif_r_ind += 1
                continue
        l_ans.append(ans)
    ans = "\n".join(map(str, l_ans))
    return ans
 
 
def main():
    params = read()
    print(solve(*params))
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
X = int(raw_input())
K = int(raw_input())
rs = map(int, raw_input().split(" "))
Q = int(raw_input())
qs = []

for q in xrange(Q):
  qs.append(map(int, raw_input().split(" ")))

l = len(qs)
for i in xrange(l):
  t = 0
  s = qs[i][1]
  end = qs[i][0]
  pre = 0
  k = 0
  while k < K:
    r = rs[k]
    if r >= end: break
    if k % 2 == 0:
      s = max(0, s - (r - pre))
    else:
      s = min(X, s + (r - pre))
    k += 1
    pre = r

  if k % 2 == 0:
    s = max(0, s - (end - pre))
  else:
    s = min(X, s + (end - pre))
  print s

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    X = II()
    K = II()
    r = ILI()
    Q = II()
    queries = [ILI() for __ in range(Q)]
    return X, K, r, Q, queries


def solve(X, K, r, Q, queries):
    l_ans = []
    r.insert(0, 0)
    dif_r = [r[i + 1] - r[i] for i in range(K)]
    dif_r.append(10 ** 9)
    for query in queries:
        t, a = query
        dif_r_ind = 0
        now_state = 0
        now_time = 0
        ans = a
        while True:
            if now_time + dif_r[dif_r_ind] > t:
                if now_state == 1:
                    ans += t - now_time
                    ans = min(X, ans)
                else:
                    ans -= t - now_time
                    ans = max(0, ans)
                break
            else:
                if now_state == 1:
                    ans += dif_r[dif_r_ind]
                    ans = min(X, ans)
                else:
                    ans -= dif_r[dif_r_ind]
                    ans = max(0, ans)
                now_time += dif_r[dif_r_ind]
                now_state = (now_state + 1) % 2
                dif_r_ind += 1
                continue
        l_ans.append(ans)
    ans = "\n".join(map(str, l_ans))
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

N=Q
L=0
R=Q-1
start=0
sign="-"

# N: 処理する区間の長さ

N0 = 2**(N-1).bit_length()
data = [0]*(2*N0)
INF = 0
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] += v

        if L & 1:
            data[L-1] += v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def query(k):
    k += N0-1
    s = INF
    while k >= 0:
        s += data[k]
        k = (k - 1) // 2
    return s

q=[]
for i in range(Q):
    t,a=p[i]
    p[i]=(a,t,i)

p.sort()
dic=[-1]*Q
for i in range(Q):
    a,t,id=p[i]
    update(i,i+1,a)
    dic[id]=i
    q.append((t,id,0))

for i in range(K):
    q.append((r[i],-1,r[i]-r[i-1]*(i>0)))

q.sort()
ans=[0]*Q
for val,id,c in q:
    if id==-1:
        if sign=="-":
            update(L,R+1,-c)
            while query(L+1)<0 and L<R:
                L+=1
            a=query(L)
            if a<0:
                update(L,L+1,-a)
            start=val
            sign="+"
        else:
            update(L,R+1,c)
            while query(R-1)>X and L<R:
                R-=1
            a=query(R)
            if a>X:
                update(R,R+1,X-a)
            start=val
            sign="-"
    else:
        pid,id=id,dic[id]
        if sign=="-":
            if id<L:
                res=max(query(L)-(val-start),0)
            elif id>R:
                res=max(query(R)-(val-start),0)
            else:
                res=max(query(id)-(val-start),0)
        else:
            if id<L:
                res=min(query(L)+(val-start),X)
            elif id>R:
                res=min(query(R)+(val-start),X)
            else:
                res=min(query(id)+(val-start),X)
        ans[pid]=res


for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
x = int(input())
k = int(input())
*R, = map(int,input().split()+[1<<30])
Q = int(input())
ta = [tuple(map(int,input().split())) for _ in range(Q)]
def f(x,l): return(max(l[0],min(l[1],x+l[2])))
L = a,b,c = 0,x,0
idx = t0 = 0
g = -1
for r in R:
    while idx < Q and ta[idx][0] < r:
        print(f(f(ta[idx][1],L)+g*(ta[idx][0]-t0),(0,x,0)));idx += 1
    d,t0 = g*(r-t0),r
    L = a,b,c = f(a,(0,x,d)),f(b,(0,x,d)),c+d
    g *= -1

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline


x, = map(int,readline().split())
k, = map(int,readline().split())
*r, = map(int,readline().split())
q, = map(int,readline().split())
r.append(1<<30)

INF = 1<<30
ID_M = (-INF,INF,0)
def compose(lst1,lst2):
    return (funcval(lst1[0],lst2),funcval(lst1[1],lst2),lst1[2]+lst2[2])

def funcval(x,lst):
    a,b,c = lst
    if x <= a-c: return a
    elif x >= b-c: return b
    else: return x+c

#seg = segment_tree_dual(q, compose, funcval, ID_M)
#seg.build([a for a,t,i in ati])

seg = (0,x,0)

tai = []
for i in range(q):
    t,a = map(int,readline().split())
    tai.append((t,a,i))

tai.sort(key=lambda x:x[0])

idx = 0
ans = [0]*q
t0 = 0
coeff = -1
for i,ri in enumerate(r):
    while idx < q and tai[idx][0] < ri:
        t,a,j = tai[idx]
        v = funcval(a,seg)
        ans[j] = min(x,max(v+coeff*(t-t0),0))
        idx += 1
        
    seg = compose(seg,(0,x,coeff*(ri-t0)))
    
    t0 = ri
    coeff *= -1    

    #print(seg)

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

Submission status: Accepted

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

x = int(input())
k = int(input())
R = [(_r, i%2) for i, _r in enumerate(map(int, input().split()))]
n = int(input())
TA = [list(map(int, input().split())) for _ in range(n)]
T, A = zip(*TA)
L = [None]*n
b = 0
for i, t in enumerate(T, 1):
  R.append((t, -i))
R.sort()
dx = 1
l, r, p, q = 0, x, 0, x
for _r, i in R:
  d = _r-b
  b = _r
  if dx == 1:
    if d <= p:
      p -= d
      q -= d
    elif d < q:
      q -= d
      l = r-q
      p = 0
    else:
      l = 0
      r = 0
      p = 0
      q = 0
  else:
    if d <= x-q:
      p += d
      q += d
    elif d < x-p:
      p += d
      r = l+(x-p)
      q = x
    else:
      l = x
      r = x
      p = x
      q = x
  if i >= 0:
    dx = i
  else:
    a = A[-i-1]
    if a < l:
      res = p
    elif a <= r:
      res = (a-l)+p
    else:
      res = q
    L[-i-1] = res
print(*L, sep="\n")