Problem:


JOI国のお散歩事情 (Walking in JOI Kingdom)

  問題

JOI 国には東西に走る 1 本の十分に長い道路がある．JOI 国の王宮が道路沿いにあり，JOI 国における道路沿いの位置は整数 A で表される．A = 0 のときは王宮の位置を表す．A > 0 のときは，王宮から東へ A メートル進んだ位置を表す．A i で表される．A1, ..., AN は全て異なる．

JOI 国では，近年国民の運動不足が問題になっている．国民の健康が気になった JOI 国の王様は，国民全員に散歩をする命令を出した．王様が命令を出すと，全ての国民は一斉に東向きまたは西向きに歩き始める．それぞれの国民がどちらの向きに歩き始めるかは，国民ごとに決まっている．全ての国民は，歩くときは 1 秒あたり 1 メートルの速度で歩く．

JOI 国の国民は皆おしゃべりが大好きである．散歩の途中にほかの国民に出会うと，その場所で立ち止まって世間話を始めてしまう．すでに立ち止まっている国民に出会った場合も同様である．一度立ち止まった国民は，再び歩き出すことはない．

JOI 国には Q 人の重要人物がいる．JOI 国の王様は，命令が出されてから T 秒後の，Q 人の重要人物の位置を把握しておきたい．命令が出されてから T 秒後の，Q 人の重要人物の位置を求めるプログラムを作成せよ．

  入力

入力は，1 + N + Q 行からなる．

1 行目には，3 つの整数 N，T，Q (1 ≦ N ≦ 100000 (= 105), 0 ≦ T ≦ 1018, 1 ≦ Q ≦ 1000，1 ≦ Q ≦ N) が空白を区切りとして書かれている．これは，JOI 国に家が N 軒あり，王様が命令を出してから T 秒後の，Q 人の重要人物の位置を把握しておきたいことを表す．

続く N 行のうち i 行目には，2 つの整数 Ai, Di (-1018 ≦ Ai ≦ 1018, Ai は 0 でない偶数, 1 ≦ Di ≦ 2) が空白を区切りとして書かれている．Ai は家 i の位置を表す偶数である．すべての i (1 ≦ i ≦ N - 1) について，Ai i+1 を満たす．Di は命令が出された後に国民 i が歩き始める方向を表す．Di = 1 のときは国民 i は東向きに歩き始める．Di = 2 のときは国民 i は西向きに歩き始める．

続く Q 行のうち i 行目には，整数 Xi (1 ≦ Xi ≦ N) が書かれている．これは，i 番目の重要人物が家 Xi に住んでいることを表す．すべての i (1 ≦ i ≦ Q - 1) について，Xi i+1 を満たす．

与えられる 5 つの入力データのうち，入力 1 では N ≦ 100，T ≦ 10000を満たす．また，入力 2 では N ≦ 5000 を満たす．また，入力 3 では，ある整数 M (1 ≦ M ≦ N - 1) があって，すべての i (1 ≦ i ≦ M) について Di = 1，すべての j (M + 1 ≦ j ≦ N) について Dj = 2 を満たす．また，入力 1，2，3 では，入力に与えられる整数の絶対値は 1000000000 (= 109) を超えない．入力 4，5 では，与えられる整数が 32 ビット符号付き整数の範囲に収まらないことに注意せよ．

  出力

出力は Q 行からなる．

i 行目 (1 ≦ i ≦ Q) には，王様が命令を出してから T 秒後の，i 番目の重要人物の位置を表す整数を出力せよ．この値が整数であることは，問題文の条件より保証されている．

  入出力例

入力例 1

  

5 5 3
-8 1
-4 2
-2 2
4 2
10 1
1
3
5

   
出力例 1

   

-6
-6
15

入力例 2

  

7 18 5
-100 1
-56 2
-34 1
-30 1
-22 1
-4 2
18 2
1
3
4
5
7

   
出力例 2

  

-82
-16
-13
-13
0

情報オリンピック日本委員会作 『第 15 回日本情報オリンピック JOI 2015/2016 予選競技課題』



Sample input:
5 5 3
-8 1
-4 2
-2 2
4 2
10 1
1
3
5


Sample output:
-6
-6
15

Submission status: Wrong Answer

Solution code:
import bisect
n, t, q = map(int, input().split())
x = [[0, 0] for _ in range(n)]
s = []
for i in range(n):
    x[i] = list(map(int, input().split()))
    if x[i - 1][1] == 1 and x[i][1] == 2:
        s.append(int((x[i - 1][0] + x[i][0]) / 2))
for _ in range(q):
    v = int(input()) - 1
    if x[v][1] == 1:
        st = bisect.bisect_left(s, x[v][0])
        print(min(x[v][0] + t, s[st]) if st < len(s) else x[v][0] + t)
    else:
        st = bisect.bisect_left(s, x[v][0])
        print(max(x[v][0] - t, s[st - 1]) if st > 0 else x[v][0] - t)

Submission status: Wrong Answer

Solution code:
n, t, q = map(int, input().split())
x = [[0, 0, 0] for _ in range(n)]
s = -10e10
for i in range(n):
    x[i] = list(map(int, input().split())) + [0]
    x[i][2] = x[i][0] + (1 if x[i][1] == 1 else -1) * t
    if x[i - 1][1] == 1 and x[i][1] == 2:
        s = int((x[i - 1][0] + x[i][0]) / 2)
        j = 1
        while x[i - j][2] > s and x[i - j][1] == 1:
            x[i - j][2] = s
            j += 1
    if x[i][1] == 2:
        x[i][2] = max(x[i][2], s)
for _ in range(q):
    print(x[int(input()) - 1][2])

Submission status: Wrong Answer

Solution code:
n, t, q = map(int, input().split())
x = [[0, 0, 0] for _ in range(n)]
s = -10e30
for i in range(n):
    x[i] = list(map(int, input().split())) + [0]
    x[i][2] = x[i][0] + (1 if x[i][1] == 1 else -1) * t
    if x[i - 1][1] == 1 and x[i][1] == 2:
        s = int((x[i - 1][0] + x[i][0]) / 2)
        j = 1
        while x[i - j][2] > s and x[i - j][1] == 1:
            x[i - j][2] = s
            j += 1
    if x[i][1] == 2:
        x[i][2] = max(x[i][2], s)
print(x)
for _ in range(q):
    print(x[int(input()) - 1][2])

Submission status: Wrong Answer

Solution code:
n, t, q = map(int, input().split())
x = [[0, 0, 0] for _ in range(n)]
s = -10e30
for i in range(n):
    x[i] = list(map(int, input().split())) + [0]
    x[i][2] = x[i][0] + (1 if x[i][1] == 1 else -1) * t
    if x[i - 1][1] == 1 and x[i][1] == 2:
        s = int((x[i - 1][0] + x[i][0]) / 2)
        j = 1
        while x[i - j][2] > s and x[i - j][1] == 1:
            x[i - j][2] = s
            j += 1
    if x[i][1] == 2:
        x[i][2] = max(x[i][2], s)
for _ in range(q):
    print(x[int(input()) - 1][2])

Submission status: Wrong Answer

Solution code:
n, t, q = map(int, input().split())
x = [[0, 0, 0] for _ in range(n)]
s = -10e40
for i in range(n):
    x[i] = list(map(int, input().split())) + [0]
    x[i][2] = x[i][0] + (1 if x[i][1] == 1 else -1) * t
    if x[i - 1][1] == 1 and x[i][1] == 2:
        s = int((x[i - 1][0] + x[i][0]) / 2)
        j = 1
        while x[i - j][2] > s and x[i - j][1] == 1:
            x[i - j][2] = s
            j += 1
    if x[i][1] == 2:
        x[i][2] = max(x[i][2], s)
for _ in range(q):
    print(x[int(input()) - 1][2])

Submission status: Wrong Answer

Solution code:
n, t, q = map(int, input().split())
x = [[0, 0, 0] for _ in range(n)]
s = -10e100
for i in range(n):
    x[i] = list(map(int, input().split())) + [0]
    x[i][2] = x[i][0] + (1 if x[i][1] == 1 else -1) * t
    if x[i - 1][1] == 1 and x[i][1] == 2:
        s = int((x[i - 1][0] + x[i][0]) / 2)
        j = 1
        while x[i - j][2] > s and x[i - j][1] == 1:
            x[i - j][2] = s
            j += 1
    if x[i][1] == 2:
        x[i][2] = max(x[i][2], s)
for _ in range(q):
    print(x[int(input()) - 1][2])

Submission status: Wrong Answer

Solution code:
n, t, q = map(int, input().split())
x = [[0, 0, 0] for _ in range(n)]
s = -float("inf")
for i in range(n):
    x[i] = list(map(int, input().split())) + [0]
    x[i][2] = x[i][0] + (1 if x[i][1] == 1 else -1) * t
    if x[i - 1][1] == 1 and x[i][1] == 2:
        s = int((x[i - 1][0] + x[i][0]) / 2)
        j = 1
        while x[i - j][2] > s and x[i - j][1] == 1:
            x[i - j][2] = s
            j += 1
    if x[i][1] == 2:
        x[i][2] = max(x[i][2], s)
for _ in range(q):
    print(x[int(input()) - 1][2])

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
n, t, q = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
qlst = [lst[int(input()) - 1] for _ in range(q)]

left = [a for a, d in lst if d == 2]
right = [a for a, d in lst if d == 1]
lenl = len(left)
lenr = len(right)
for a, d in qlst:
  if d == 1:
    coll_ind = bl(left, a)
    if coll_ind >= lenl:
      print(a + t)
    else:
      coll = left[coll_ind]
      coll2 = right[bl(right, coll) - 1]
      coll_pos = (coll + coll2) // 2
      print(min(a + t, coll_pos))

  else:
    coll_ind = bl(right, a) - 1
    if coll_ind == -1:
      print(a - t)
    else:
      coll = right[coll_ind]
      coll2 = left[bl(left, coll)]
      coll_pos = (coll + coll2) // 2
      print(max(a - t, coll_pos))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

N, T, Q = map(int, readline().split())
P = [list(map(int, readline().split())) for i in range(N)]
QS = [P[int(readline())-1] for i in range(Q)]
prv = 1
R = {}
A = []; B = []
for x, t in P:
    if prv == t:
        if t == 1:
            A.append(x)
        else:
            B.append(x)
    else:
        if prv == 2:
            y = ((A[-1] if A else -10**19) + (B[0] if B else 10**19)) >> 1
            for z in A:
                R[z] = min(z+T, y)
            for z in B:
                R[z] = max(z-T, y)
            A = [x]; B = []
        else:
            B.append(x)
    prv = t
if A or B:
    y = ((A[-1] if A else -10**19) + (B[0] if B else 10**19)) >> 1
    for z in A:
        R[z] = min(z+T, y)
    for z in B:
        R[z] = max(z-T, y)

for x in QS:
    write("%d\n" % R[x[0]])

Submission status: Accepted

Solution code:
#D
import bisect
N,T,Q = map(int,input().split())
AD = [list(map(int,input().split())) for i in range(N)]
X = [int(input()) for i in range(Q)]

wall = []
for i in range(N-1):
    a1,d1 = AD[i]
    a2,d2 = AD[i+1]
    
    if d1 == 1 and d2 == 2:
        if T > (a2-a1)//2:
            wall.append((a1+a2)//2)
        
wlen = len(wall)
for x in X:
    ind = x-1
    a,d = AD[ind]
    if d == 1:
        bind = bisect.bisect_left(wall,a)
        if bind == wlen:
            print(a+T)
        else:
            wa = wall[bind]
            if wa <= a+T:
                print(wa)
            else:
                print(a+T)
    else:
        bind = bisect.bisect_left(wall,a)-1
        if bind == -1:
            print(a-T)
        else:
            wa = wall[bind]
            if wa >= a-T:
                print(wa)
            else:
                print(a-T)

Submission status: Runtime Error

Solution code:
n, t, q = map(int, input().split())
x = [[0, 0, 0] for _ in range(n)]
s = -10e10
for i in range(n):
    x[i] = list(map(long, input().split())) + [0]
    x[i][2] = x[i][0] + (1 if x[i][1] == 1 else -1) * t
    if x[i - 1][1] == 1 and x[i][1] == 2:
        s = int((x[i - 1][0] + x[i][0]) / 2)
        j = 1
        while x[i - j][2] > s and x[i - j][1] == 1:
            x[i - j][2] = s
            j += 1
    if x[i][1] == 2:
        x[i][2] = max(x[i][2], s)
print(x)
for _ in range(q):
    print(x[int(input()) - 1][2])