Problem:


Score : 600 points

Problem Statement

There is a grid of squares with H+1 horizontal rows and W vertical columns.

You will start at one of the squares in the top row and repeat moving one square right or down. However, for each integer i from 1 through H, you cannot move down from the A_i-th, (A_i + 1)-th, \ldots, B_i-th squares from the left in the i-th row from the top.

For each integer k from 1 through H, find the minimum number of moves needed to reach one of the squares in the (k+1)-th row from the top. (The starting square can be chosen individually for each case.) If, starting from any square in the top row, none of the squares in the (k+1)-th row can be reached, print -1 instead.

Constraints

1 \leq H,W \leq 2\times 10^5

1 \leq A_i \leq B_i \leq W

Input

Input is given from Standard Input in the following format:

H W
A_1 B_1
A_2 B_2
:
A_H B_H

Output

Print H lines. The i-th line should contain the answer for the case k=i.

Sample Input 1

4 4
2 4
1 1
2 3
2 4

Sample Output 1

1
3
6
-1

Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

For k=1, we need one move such as (1,1) → (2,1).

For k=2, we need three moves such as (1,1) → (2,1) → (2,2) → (3,2).

For k=3, we need six moves such as (1,1) → (2,1) → (2,2) → (3,2) → (3,3) → (3,4) → (4,4).

For k=4, it is impossible to reach any square in the fifth row from the top.



Sample input:
4 4
2 4
1 1
2 3
2 4


Sample output:
1
3
6
-1

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(h)]
dp = [None]*h
v = 1
i = 0
for a,b in ab:
    if a<=v<=b:
        v = b+1
    dp[i] = v
    i += 1
dp2 = [None]*h
done = [0]*h
for i in range(h-1,-1,-1):
    if done[i]:
        continue
    v = w
    l = []
    for j in range(i, -1, -1):
        a,b = ab[j]
        if v==w:
            l.append(j)
        if a<=v<=b:
            v = a-1
    for ind in l:
        dp2[ind] = v
        done[ind] = 1
dp,dp2
ans = [None]*h
for i in range(h):
    if dp[i]>w:
        ans[i] = -1
    else:
#         if dp[i]>=dp2[i]:
        ans[i] = (i+1) + (dp[i]-dp2[i])
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ABs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(H)]

now = 0
out = False
for i, AB in enumerate(ABs):
    if out == True:
        print(-1)
        continue
    
    if AB[0] > now or AB[1] < now:
        print(i+1+now)
    elif AB[1]+1 <= W-1:
        now = AB[1]+1
        print(i+1+now)
    else:
        print(-1)
        out = True

Submission status: Wrong Answer

Solution code:
class segment_tree:
    def __init__(self, N, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        
        self.N0 = 1<<(N-1).bit_length()
        self.dat = [self.e_M]*(2*self.N0)
    
    # 長さNの配列 initial で初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])

    # a_k の値を x に更新
    def update(self,k,x):
        k += self.N0
        self.dat[k] = x
        k //= 2
        while k:
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
            k //= 2

    # 区間[L,R]をopでまとめる
    def query(self,L,R):
        L += self.N0; R += self.N0 + 1 
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.dat[R],sr)
            if L & 1:
                sl = self.op_M(sl,self.dat[L])
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)

    def get(self, k): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]

class BIT: #0-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [i&-i for i in range((n+1))]
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x
    
class stdmap:
    def __init__(self, n):
        self.size = n+1
        self.keys = set()
        self.B = BIT(n+1) #存在すれば 1、しないなら 0
        self.dic = [0]*(n+1) # 値域
    
    def __contains__(self, k):
        return k in self.keys

    def insert(self,a,b): # 値 a に b を上書き
        if a not in self.keys:
            self.B.add(a,1)
            self.keys.add(a)
        self.dic[a] = b

    def remove(self,a): # a を取り除く
        self.keys.remove(a)
        self.B.add(a,-1)

    def lower_bound(self,k): # k 以上の最小のkeyを求める
        return self.B.bisect_left(self.B.get_sum(k))
        
    def kth_key(self,k): # k 番目に小さい元のkeyを求める
        return self.B.bisect_left(k)

    def kth_value(self,k): # k 番目に小さい元のmap先を求める
        return self.dic[self.B.bisect_left(k)]

    def prev_key(self,k): #一個前の元のkeyを求める
        idx = self.B.get_sum(k)
        assert idx != 0
        return self.B.bisect_left(idx-1)

    def next_key(self,k):
        idx = self.B.get_sum(k)
        assert idx != self.size
        return self.B.bisect_left(idx+1)

    def __getitem__(self,item):
        return self.dic[item]


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

h,w = map(int,readline().split())

b = stdmap(w+2)
b.dic = [0]*(w+3) # 値域
b.keys = set(range(w+2))

INF = 1<<31
seg = segment_tree(w+2, min, INF)
seg.build([INF]+[0]*w+[INF])


for i in range(1,h+1):
    p,q = map(int,readline().split())

    v = b.B.get_sum(p-1)
    idx = b.kth_key(v)
    
    x = b.next_key(idx)
    val = INF
    while x <= q:
        #print(x,b.dic[x]-x,"x,val")
        val = min(val,b.dic[x]-x)
        seg.update(x,INF)
        b.remove(x)
        x = b.next_key(x)
    
    if q < w:
        b.insert(q+1,val+q+1)
        seg.update(q+1,val+q+1)
    
    #print(b.keys)
    #print(seg.dat)
    #print(q,val,"q,val")    

    v = seg.dat[1]
    #print(v,i)
    if v>=INF:
        print(-1)
    else:
        print(v+i)
    
    #print()

Submission status: Wrong Answer

Solution code:
import sys


def main():
    # input = sys.stdin.buffer.readline
    h, w = map(int, input().split())
    a = [0] * h
    b = [0] * h
    for i in range(h):
        a[i], b[i] = map(int, input().split())
    cannot_reach = False
    start_fixed = False
    a_touched_zero = False
    min_a = 10 ** 6
    b_touched_w = False
    dist = 0
    pos = 0
    for k in range(1, h + 1):
        if cannot_reach:
            print(-1)
        elif start_fixed:
            if pos < a[k - 1] or b[k - 1] < pos:
                dist += 1
                print(dist)
            elif b[k - 1] == w:
                cannot_reach = True
                print(-1)
                continue
            else:
                dist += b[k - 1] + 1 - pos + 1
                print(dist)
                pos = b[k - 1] + 1
        else:
            if a[k - 1] == 1 and b[k - 1] == w:
                cannot_reach = True
                print(-1)
                continue
            if a[k - 1] == 1:
                a_touched_zero = True
                if b_touched_w:
                    start_fixed = True
                    print(k + max(0, b[k - 1] - min_a + 2))
                    dist = k + max(0, b[k - 1] - min_a + 2)
                    pos = b[k - 1] + 1
                    continue
            if b[k - 1] == w:
                b_touched_w = True
                if a_touched_zero:
                    cannot_reach = True
                    print(-1)
                    continue
            min_a = min(min_a, a[k - 1])
            print(k)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import time
time0=time.time()

H,W=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(H)]

ANS=[1<<30]*H

def start(NOW):
    SCORE=0
    for i in range(H):
        if D[i][0]<=NOW<=D[i][1]:
            SCORE+=D[i][1]+1-NOW+1
            NOW=D[i][1]+1
        else:
            SCORE+=1

        if NOW==W+1:
            return

        if ANS[i]>SCORE:
            ANS[i]=SCORE
        #else:
        #    return

S=[]
for x,y in D:
    if x>=2:
        S.append(x-1)
    if y<W:
        S.append(y+1)

for s in set(S):
    start(s)

    if time.time()-time0>1.8:
        break
    
for a in ANS:
    if a!=1<<30:
        print(a)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

h,w = list(map(int,input().split()))
start = 1
cnt = 0

for _ in range(h):
  a,b = list(map(int,input().split()))
  
  if a>1:
    good = a-1
  else:
    good = a+1
    
  if start>=a and start<=b:
    start = b+1
    
  if start <= w:
    print(start + cnt)
  else:
    print(-1)
    
  cnt += 1

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import time
time0=time.time()

H,W=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(H)]

ANS=[1<<30]*H

def start(NOW):
    SCORE=0
    for i in range(H):
        if D[i][0]<=NOW<=D[i][1]:
            SCORE+=D[i][1]+1-NOW+1
            NOW=D[i][1]+1
        else:
            SCORE+=1

        if NOW==W+1:
            return

        if ANS[i]>SCORE:
            ANS[i]=SCORE
        #else:
        #    return

for i in range(1,W+1):
    start(i)

    if time.time()-time0<1.8:
        break
    
for a in ANS:
    if a!=1<<30:
        print(a)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(h)]

# 貪欲でシミュレーション

pos = 1
steps = 0
downable = True

for a, b in AB:
  if not downable:
    print(-1)
    continue
  if pos < a or b < pos:
    steps += 1
    print(steps)
  elif a <= pos <= b:
    steps += b - pos + 2 # 右へ：b - pos + 1、下へ1
    pos = b + 1
    if b == w:
      print(-1) 
      downable = False
    else:
      print(steps)

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))
AB = [list(map(int,input().split())) for i in range(H)]

ans = 0
p = 0
for i in range(H):
    if W <= p:
        print(-1)
        continue
    A,B = AB[i]
    A -= 1
    B -= 1
    if A <= p <= B:
        ans += B-p+2
        p = B+1
        if W <= p:
            print(-1)
        else:
            print(ans)
    else:
        ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
def nextstep(ANS, START, A, B):
    cnt, GOAL = w, set()
    for i in start:
        if A <= i <= B:
            if B < w:
                cnt = min(cnt, B - i + 2)
                GOAL.add(B + 1)
        else:
            cnt = 1
            GOAL.add(i)
    return cnt + ANS, GOAL


h, w = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(h)]

ans, start = 0, set(i for i in range(1, w + 1))
for a, b in ab:
    ans, start = nextstep(ans, start, a, b)
    print(ans if len(start) > 0 else -1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import time
time0=time.time()

H,W=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(H)]

ANS=[1<<30]*H

def start(NOW):
    SCORE=0
    for i in range(H):
        if D[i][0]<=NOW<=D[i][1]:
            SCORE+=D[i][1]+1-NOW+1
            NOW=D[i][1]+1
        else:
            SCORE+=1

        if NOW==W+1:
            return

        if ANS[i]>SCORE:
            ANS[i]=SCORE
        #else:
        #    return

S=[]
for x,y in D:
    if x>=2:
        S.append(x-1)
    if y<W:
        S.append(y+1)

for s in set(S):
    start(s)

    if time.time()-time0<1.8:
        break
    
for a in ANS:
    if a!=1<<30:
        print(a)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
def nextstep(ANS, START, A,B):
    cnt, GOAL = w, set()
    for i in start:
        if A <= i <= B:
            if B < w:
                cnt = min(cnt, B - i + 2)
                GOAL.add(B + 1)
        else:
            cnt = 1
            GOAL.add(i)
    return cnt + ANS, GOAL


h, w = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(h)]

ans, start = 0, set(i for i in range(1, w))
for a, b in ab:
    ans, start = nextstep(ans, start, a, b)
    print(ans if len(start) > 0 else - 1)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
def solve():
    h, w = map(int, input().split())
    a = []
    b = []
    ans = 0
    for i in range(h):
        x, y = map(int, input().split())
        a.append(x - 1)
        b.append(y - 1)
    pos = 0
    for i in range(h):
        if ans > -1:
            if a[i] <= pos and pos <= b[i]:
                ans += b[i] - pos + 1
                pos = b[i] + 1
            if pos >= w:
                ans = -1
            else:
                ans += 1
        print(ans)
t = 1
while t > 0:
    solve()
    t -= 1

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
T=[0]*H
for i in range(H):
    a,b=map(int,input().split())
    T[i]=(a,b)

D=[-1]*H
x=1
for i in range(H):
    a,b=T[i]
    if a<=x<=b:
        x=b+1
    D[i]=x

Y=[-1]*H
for i in range(H):
    if D[i]<=W:
        Y[i]=i+D[i]

print("\n".join(map(str,Y)))

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
x=1
for k in range(h):
    if x==0:
        print(-1)
        continue
    a,b=map(int,input().split())
    if x<a or b<x:
        print(x+k)
    elif b<w:
        x=b+1
        print(x+k)
    else:
        x=0
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    obstacle = [(map(int, input().split())) for _ in range(H)]
    y = 1
    t = 0
    ans = [-1] * H
    for i in range(H):
        A, B = obstacle[i]
        if y < A or y > B:
            t += 1
        else:
            t += B - y + 2
            y = B + 1
            if y > W:
                break
        ans[i] = t
    for i in range(H):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import time
time0=time.time()

H,W=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(H)]

ANS=[1<<30]*H

def start(NOW):
    SCORE=0
    for i in range(H):
        if D[i][0]<=NOW<=D[i][1]:
            SCORE+=D[i][1]+1-NOW+1
            NOW=D[i][1]+1
        else:
            SCORE+=1

        if NOW==W+1:
            return

        if ANS[i]>SCORE:
            ANS[i]=SCORE
        else:
            return

S=[]
for x,y in D:
    if x>=2:
        S.append(x-1)
    if y<W:
        S.append(y+1)

for s in S:
    start(s)

    if time.time()-time0<1.8:
        break
    
for a in ANS:
    if a!=1<<30:
        print(a)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10
    
    H,W = LMIIS()
    '''
    (y,x)からy+1行目までの移動
    l,r : y+1行目の制限範囲
    if x<l: (y+1,x) コスト+1
    if l <= x <= r and r < W: (y+1,r+1) コスト + (r-x+1)
    if l <= x <= r and r == W: -1
    if r < x : (y+1,x) コスト+1
    '''

    out = [-1] * H
    #初期位置決定
    a,b = LMIIS()
    if 1 < a:
        x = 1
    elif b < W:
        x = W
    else:
        print('\n'.join(map(str,out)))
        return
    out[0] = 1

    for i in range(H-1):
        l,r = LMIIS()
        if x < l or r < x:
            out[i+1] = out[i] + 1
        elif r < W:
            out[i+1] = out[i] + r - x + 2
            x = r + 1
        else:
            break
    print('\n'.join(map(str,out)))


    


    
main()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
you=1
ans=0
for i in range(h):
    if ans==-1:
        a,b=map(int,input().split())
        print(ans)
    else:
        a,b=map(int,input().split())
        if you<a:
            ans+=1
        elif you>=a:
            tmp=you
            you=b+1
            if you<=w:
                ans+=you-tmp+1
            elif you>w:
                ans=-1
        print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())

# どこからスタートするか
A = []
B = []
L = W
R = 1
st = W
m = H+1
for i in range(H):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

    L = min(L, a)
    R = max(R, b)
    if L == 1 and R == W:
        m = min(i, m)
    else:
        if R < W:
            st = W
        else:
            st = L-1
# print(st, m)

c = 0
flg = False
for i in range(H):
    if A[i] <= st <= B[i]:
        if B[i] == W:
            flg = True
        c += B[i]-st+1
        st = B[i]+1
    c += 1
    if flg:
        print(-1)
    else:
        print(c)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import time
time0=time.time()

H,W=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(H)]

ANS=[1<<30]*H

def start(x):
    NOW=1
    SCORE=0
    for i in range(H):
        if D[i][0]<=NOW<=D[i][1]:
            SCORE+=D[i][1]+1-NOW+1
            NOW=D[i][1]+1
        else:
            SCORE+=1

        if NOW==W+1:
            return

        if ANS[i]>SCORE:
            ANS[i]=SCORE
        else:
            return

S=[]
for x,y in D:
    if x>=2:
        S.append(x-1)
    if y<W:
        S.append(y+1)

for s in S:
    start(s)

    if time.time()-time0<1.8:
        break
    
for a in ANS:
    if a!=1<<30:
        print(a)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import time
time0=time.time()

H,W=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(H)]

ANS=[1<<30]*H

def start(x):
    NOW=1
    SCORE=0
    for i in range(H):
        if D[i][0]<=NOW<=D[i][1]:
            SCORE+=D[i][1]+1-NOW+1
            NOW=D[i][1]+1
        else:
            SCORE+=1

        if NOW==W+1:
            return

        if ANS[i]>SCORE:
            ANS[i]=SCORE
        else:
            return

S=[]
for x,y in D:
    if x>2:
        S.append(x-1)
    if y<W:
        S.append(y+1)

for s in S:
    start(s)

    if time.time()-time0<1.8:
        break
    
for a in ANS:
    if a!=1<<30:
        print(a)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
you=1
ans=0
for i in range(h):
    if ans==-1:
        print(ans)
    else:
        a,b=map(int,input().split())
        if you<a:
            ans+=1
        elif you>=a:
            tmp=you
            you=b+1
            if you<=w:
                ans+=you-tmp+1
            elif you>w:
                ans=-1
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
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 SI(): return sys.stdin.readline()[:-1]

inf=10**9
h,w=MI()
lr=[]
for _ in range(h):
    l,r=MI()
    lr.append((l-1,r))
ans=[inf]*h
j=k=0
now=0
for i,(l,r) in enumerate(lr):
    k=max(k,r)
    if l<=j<r:
        if r==w:break
        else:
            if i:now+=r-j
            j=r
    now+=1
    if k<w:ans[i]=i+1
    else:ans[i]=now
for i in range(h):
    if ans[i]==inf:ans[i]=-1
for a in ans:print(a)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
now = 0
INF = 10**9
d = [INF] * (w + 1)
for i in range(h):
    a, b = map(int, input().split())
    a -= 1
    if a <= now:
        for j in range(now, b):
            d[j] = i
        now = max(b, now)
now = 0
for i in range(h):
    for j in range(now, w + 1):
        now = j
        if d[j] > i:
            break
    print(j + i + 1 if now < w else -1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


H,W = MI()
AB = [tuple(MI()) for i in range(H)]

X = []
x = 1
for i in range(H):
    a,b = AB[i]
    if a <= x <= b:
        X += [i]*(b-x+1)
        x = b+1

if len(X) == 0:
    for _ in range(H):
        print(-1)
        exit()

m = max(X)

r = 0
for i in range(len(X)):
    if i == 0:
        for j in range(X[i]):
            print(j+1)
        r = X[i]
    else:
        if X[i] == X[i-1]:
            r += 1
        else:
            for j in range(X[i]-X[i-1]):
                print(r+2+j)
            r = r+2+X[i]-X[i-1]-1

if len(X) < W:
    for i in range(H-max(X)):
        print(r+2+i)

else:
    for _ in range(H-max(X)):
        print(-1)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
you=1
ans=0
for i in range(h):
    a,b=map(int,input().split())
    if you<a:
        ans+=1
    elif you>=a:
        tmp=you
        you=b+1
        if you<=w:
            ans+=you-tmp+1
        elif you>w:
            ans=-1
    print(ans)

Submission status: Wrong Answer

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

h,w = map(int,input().split())

x = 1
A = []
B = []
kouho = [1]
for i in range(h):
    AA,BB = map(int,input().split())
    A.append(AA)
    B.append(BB)
    if i%1000 == 0:
        kouho.append(AA)
        kouho.append(BB)


dp = [10**6] * h
for start in kouho:
    x = start
    for i in range(h):
        a,b = A[i],B[i]
        if a <= x <= b:
            x = b+1
        if x != w+1:
            dp[i] = min(dp[i],x+i)

for i in range(h):
    if dp[i] == 10**6:
        print(-1)
    else:
        print(dp[i])

Submission status: Wrong Answer

Solution code:
def main():
    H, W = list(map(int, input().split()))
    constraints = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(H)]
    cur, count = 0, 0
    ans = [-1] * H
    for h in range(H):
        a, b = constraints[h]
        if b < cur or cur < a:
            count += 1
            ans[h] = count
            continue
        if b == W - 1:
            break
        count += b - cur + 2
        ans[h] = count
        cur = b + 1
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

h,w = map(int,input().split())

x = 1
A = []
B = []
kouho = [1]
for i in range(h):
    AA,BB = map(int,input().split())
    A.append(AA)
    B.append(BB)
    if i <= 100:
        kouho.append(AA)
        kouho.append(BB)


dp = [10**6] * h
for start in kouho:
    x = start
    for i in range(h):
        a,b = A[i],B[i]
        if a <= x <= b:
            x = b+1
        if x != w+1:
            dp[i] = min(dp[i],x+i)

for i in range(h):
    if dp[i] == 10**6:
        print(-1)
    else:
        print(dp[i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
now = 0
INF = 10**9
d = [INF] * (w + 1)
for i in range(h):
    a, b = map(int, input().split())
    a -= 1
    if a <= now:
        for j in range(now, b):
            d[j] = i
        now = b
now = 0
for i in range(h):
    for j in range(now, w + 1):
        now = j
        if d[j] > i:
            break
    print(j + i + 1 if now < w else -1)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(H)]
x,r,f=0,0,0
for a,b in AB:
    a-=1
    b-=1
    if a<=x<=b:
        if f or b==W-1:
            f=1
            print(-1)
        else:
            r+=b-x+2
            print(r)
            x=b+1
    else:
        r+=1
        print(r)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
now = 0
d = [0] * (w + 1)
for i in range(h):
    a, b = map(int, input().split())
    a -= 1
    if a <= now:
        for j in range(now, b):
            d[j] = i
        now = b
now = 0
for i in range(h):
    for j in range(now, w + 1):
        now = j
        if d[j] > i:
            break
    print(j + i + 1 if now < w else -1)

Submission status: Wrong Answer

Solution code:
def read():
    H, W = map(int, input().split(' '))
    As = []
    for _ in range(H):
        A, B = map(int, input().split(' '))
        As.append((A, B))
    return H, W, As


def func(H, W, As):
    x = 1
    ans = 0
    for A, B in As:
        if ans == -1:
            pass
        elif x < A:
            ans += 1
        elif x <= B:
            ans += (B + 1 - x + 1) 
            x = B + 1
        else:
            ans += 1
        if x > W:
            ans = -1
        print(ans)

if __name__ == '__main__':
    H, W, As = read()
    func(H, W, As)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())

walls = []

for _ in range(H):
	A, B = map(int, input().split())
	walls.append((A - 1, B - 1))

pos = 0
for k in range(H):
	A, B = walls[k]
	if pos >= A:
		pos = B + 1
	if pos >= W:
		print(-1)
	else:
		print(k + 1 + pos)

Submission status: Wrong Answer

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

h,w=map(int,input().split())

L=[]
for i in range(h):
    a,b=map(int,input().split())
    L.append((a-1,b-1))

ans=[-1]*h

count=0
if L[0][0]!=0:
    now=0
else:
    now=L[0][1]+1

for i in range(h):
    if now>=w:
        break

    count+=1
    ans[i]=count
    if i!=h-1:
        if L[i+1][0]<=now<=L[i+1][1]:
            count += L[i + 1][1] - now + 1
            now=L[i+1][1]+1

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
H, W, *AB = map(int, open(0).read().split())

x = 1
moved = 0
for a, b in zip(*[iter(AB)] * 2):
    if x < a or x > b:
        moved += 1
    else:
        moved += b - x + 2
        x = b + 1
    print(moved) if x <= W else print(-1)

Submission status: Wrong Answer

Solution code:
from sys import exit

h, w = map(int, input().split())
l = []
for _ in range(h):
    a, b = map(int, input().split())
    l.append([a-1, b-1])

pos_h = 0
if l[0][0] == 0:
    if l[0][1] == w - 1:
        for _ in range(h):
            print(-1)
        exit()
    
    pos_w = l[0][1] + 1
else:
    pos_w = l[0][0] - 1

res = [-1] * h
cnt = 0
while pos_h < h and pos_w < w:
    if pos_h > 0:
        if res[pos_h-1] == -1:
            res[pos_h-1] = cnt

    if pos_w < l[pos_h][0] or l[pos_h][1] < pos_w:
        pos_h += 1
    else:
        pos_w += 1
    
    cnt += 1

for v in res:
    print(v)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())

l = [tuple(map(int, input().split())) for _ in range(H)]
ans = 0
pos = 1
cost = 0
nr = False

for i, (left, right) in enumerate(l):
    if left<=pos<=right:
        if pos<W and right<W:
            if i:
                cost += (right+1)-pos
            pos = right+1
        else:
            nr = True
    cost += 1
    if nr:
        print(-1)
    else:
        print(cost)

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline

H, W = map(int, input().split())

w = 1
count = 0
for k in range(1, H + 1):
    A, B = map(int, input().split())
    if count == -1:
        print (-1)
        continue

    if w < A:
        count += 1
        print (count)
    elif B < w <= W:
        count += 1
        print (count)
    else: # A <= w <= B
        count += (B - w) + 1
        w = B + 1
        if w <= W:
            count += 1
            print (count)
        else:
            count = -1
            print (count)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
que = []
for i in range(h):
    a, b = map(int, input().split())
    que.append((a, b))
now = 1
cnt = 0
data = []
for a, b in que:
    if now < a:
        cnt += 1
        data.append(cnt)
    elif a <= now <= b:
        old_now = now
        now = b+1
        if now > w:
            break
        else:
            cnt += now-old_now
            cnt += 1
            data.append(cnt)
    elif now > b:
        cnt += 1
        data.append(cnt)

l = len(data)

data += [-1]*(h-l)

for x in data:
    print(x)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
AB=[tuple(map(int,input().split())) for _ in range(H)]

ans=[0]
pos=0
for i in range(H):
  if AB[i][0]-1 > pos:
    ans.append(ans[-1]+1)
    continue
  if AB[i][1]==W:
    ans.extend([-1]*(H-i))
    break
  ans.append(ans[-1]+AB[i][1]-1-pos+2)
  pos = AB[i][1]
  
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int,input().split())
C = [list(map(int,input().split())) for i in range(h)]
for i in range(h):
    for j in range(2):
        C[i][j] -= 1


ANS = []
ind = 0
for i in range(h):
    if C[i][0] <= ind <= C[i][1]:
        ind = C[i][1] + 1
    if ind == w:
        break
    ANS.append(i + ind + 1)

for i in ANS:
    print(i)
for i in range(h-len(ANS)):
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


h,w = map(int,readline().split())
data = list(map(int,read().split()))

ans = []
left = 1

it = iter(data)
for i,a,b in zip(range(1,h+1), it,it):
    if(left==w+1):
        ans.append(-1)
        continue
    if(left>=a):
        left = max(left,b+1)
    if(left==w+1):
        ans.append(-1)
        continue

    ans.append(i+left-1)
    print(i,left,i+left-1)

print('\n'.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

h, w = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(h)]

cost = 0
cur_i = 1
ans = []
# 貪欲
for row_num in range(h):
    a, b = ab[row_num]
    if a <= cur_i <= b:
        cost += (b + 1 - cur_i)
        cur_i = b + 1
    if cur_i > w:
        ans.append(-1)
    else:
        cost += 1
        ans.append(cost)

print("\n".join(list(map(str, ans))))