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:
class BalancingTree:
    def __init__(self, n):
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def debug(self):
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot , nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1,nd_.cnt)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def append(self, v):
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v):
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v):
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    @property
    def max(self):
        return self.find_l((1<<self.N)-1)

    @property
    def min(self):
        return self.find_r(-1)

    @property
    def sum(self):
        return self.root.sum-self.root.value+1

    @property
    def size(self):
        return self.root.cnt-1

    def delete(self, v, nd = None, prev = None):
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if not prev.left:
                prev.right=None
            elif not prev.right:
                prev.left=None
            else:
                if nd.pivot==prev.left.pivot:
                    prev.left=None
                else:
                    prev.right=None
        elif nd.right:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)
        else:
            nd.value = self.rightmost(nd.left).value
            self.delete(nd.value - 1, nd.left, nd)


    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None


import sys,heapq

input=sys.stdin.readline

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

exist=[True for i in range(W+1)]

que=[(0,i) for i in range(1,W+1)]
heapq.heapify(que)

BT=BalancingTree(40)

for i in range(1,W+1):
    tmp=(i<<20)+i
    BT.append(tmp)


erase=set()
for i in range(H):
    a,b=ban[i]
    erasemax=(-1,-1)
    while True:
        val=BT.find_r(a<<20)
        pos=val>>20
        fr=val%(1<<20)
        if pos<=b:
            erasemax=max(erasemax,(pos-fr,fr))
            exist[fr]=False
            BT.delete(val)
        else:
            if pos>b+1 and erasemax[1]!=-1 and b+1<=W:
                BT.append(((b+1)<<20)+erasemax[1])
                erase.add(erasemax)
                heapq.heappush(que,(b+1-erasemax[1],erasemax[1]))
                exist[erasemax[1]]=True
            break

    while que and (not exist[que[0][1]] or que[0] in erase):
        heapq.heappop(que)

    if que:
        res = i+1+que[0][0]
        print(res)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

INF = 10 ** 6
H, W = map(int,input().split())
A = []
B = []
for i in range(H):
    a, b = map(int,input().split())
    A.append(a-1)
    B.append(b-1)
 
ans = [INF] * H

def dfs(x, y, cnt, cnt2):
    if x != 0 and ans[x-1] == INF:
        ans[x-1] = min(ans[x-1], cnt - cnt2)
    if x == H:
        for i in ans:
            if i == INF:
                print(-1)
            else:
                print(i)
        sys.exit()
    nx = x + 1
    ny = y
    if not A[x] <= ny <= B[x]:
        dfs(nx, ny, cnt + 1, cnt2)
    elif B[x] != W-1:
        nx = x + 1
        ny = B[x] + 1
        if nx == 0:
            cnt2 += B[x] + 1 - y
        dfs(nx, ny, cnt + B[x] + 2 - y, cnt2)
 
dfs(0, 0, 0, 0)
 
for i in ans:
    if i == INF:
        print(-1)
    else:
        print(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 = max(b, now)
# print(d)
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)]

ans = [10**15]*(H)

for x in [1,AB[0][0]-1,AB[0][1]+1,W]:
    if x > W or x < 1:
        break
    cost=0
    for i in range(H):
        a,b = AB[i]
        if a<=x and x<=b:
            cost+=b-x+1
            x=b+1
            if x > W:
                break
        cost+=1
        ans[i] = min(ans[i],cost)


for i in range(len(ans)):
    if ans[i]==10**15:
        ans[i]=-1
    print(ans[i])

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
USE=set()

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
        
        USE.add((NOW,i))

        if ANS[i]>SCORE:
            ANS[i]=SCORE
        elif (NOW,i) in USE:
            return
        #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:
H,W = map(int,input().split())

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

ans = [10**15]*(H)

for x in [1,AB[0][0]-1,AB[0][1]+1,W]:
    print(x)
    if x > W or x < 1:
        break
    cost=0
    for i in range(H):
        a,b = AB[i]
        if a<=x and x<=b:
            cost+=b-x+1
            x=b+1
            if x > W:
                break
        cost+=1
        ans[i] = min(ans[i],cost)


for i in range(len(ans)):
    if ans[i]==10**15:
        ans[i]=-1
    print(ans[i])

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,w]
used = [True]*(w+1)
for i in range(h):
    AA,BB = map(int,input().split())
    A.append(AA)
    B.append(BB)
    if len(kouho) <= 400 or i >= h-100:
        if AA != 1 and used[AA-1]:
            kouho.append(AA-1)
            used[AA-1] = False
        if BB != w and used[BB+1]:
            kouho.append(BB+1)
            used[BB+1] = False


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-start+i+1)

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

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    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())

    ans = 0
    x = 1
    for k in range(H):
        if A[k] <= x and x <= B[k]:
            if k > 0:
                ans += B[k] - x + 1
            x = B[k] + 1
        ans += 1
        if x > W:
            print(-1)
        else:
            print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
h_stopped = [0]*H

dp = [[10**18]*(H+1) for _ in range(2)]
dp[0][0] = 0
dp[1][0] = 0
left, right = 1, W
rmax = 0
for h in range(1, H+1):
    a, b = mapint()
    rmax = max(rmax, b)
    if left==1:
        if a!=1:
            dp[0][h] = dp[0][h-1] + 1
        else:
            left = b + 1
            if left>=W+1:
                break
            dp[0][h] = dp[0][h-1] + (b-a+2)
    else:
        if a>left:
            dp[0][h] = dp[0][h-1] + 1
        else:
            left = b + 1
            if left>=W+1:
                break
            dp[0][h] = dp[0][h-1] + (b-a+2)
    if rmax!=W:
        dp[1][h] = dp[1][h-1] + 1

for i in range(1, H+1):
    ans = min(dp[0][i], dp[1][i])
    print(ans) if ans<=10**17 else print(-1)

Submission status: Wrong Answer

Solution code:
H, W = (int(x) for x in input().split())
a = []
b = []
for _ in range(H):
    _input = input().split()
    a.append(int(_input[0])-1)
    b.append(int(_input[1])-1)
pos = [0, 0]
num = 0
for i in range(H):
    if num==-1:
        print(num)
    while(pos[0]!=i+1):
        if (a[i] <= pos[1]) and (pos[1] <= b[i]):
            diff = b[i] - pos[1] + 1
            pos[1] += diff
            num += diff
        else:
            pos[0] += 1
            num += 1
            if pos[0]==i+1:
                break
        if pos[1] >= W:
            num = -1
            break

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
USE=set()

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
        
        USE.add(NOW)

        if ANS[i]>SCORE:
            ANS[i]=SCORE
        elif NOW in USE:
            return
        #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:
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())

    idx = b.B.get_sum(p-1)+1
    x = b.kth_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.kth_key(idx)
    
    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:
def main():  
    h, w = map(int, input().split())
    j = 0
    for i in range(1, h + 1):
        a, b = map(int, input().split())
        if j > w:
            print(-1)
            continue

        if a <= j + 1 <= b:
            j = b
            if j < w:
                print(i + j)
            else:
                print(-1)
            
            
        else:
            print(i + j)

    
    
            

    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
""" F
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(H, W):
    c = 0
    A, B = readIntegerSet(2)
    x = 0 if A > 1 else B

    for k in range(H):
        if k > 0:
            A, B = readIntegerSet(2)
        if x > W-1:
            print(-1)
            continue
        if x >= A-1 and x <= B-1:
            x0 = x
            x = B
            if x > W-1:
                print(-1)
                continue
            c += (x - x0 + 1)
        else:
            c += 1
        print(c)



if __name__ == "__main__":
    _H, _W = readIntegerSet(2)

    main(_H, _W)

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,w]
for i in range(h):
    AA,BB = map(int,input().split())
    A.append(AA)
    B.append(BB)
    if len(kouho) <= 300 or i%1000 == 0:
        if AA != 1:
            kouho.append(AA-1)
        if BB != w:
            kouho.append(BB+1)


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-start+i+1)

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 = 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])
        else:
            ans[i] = (i+1) + (w-dp2[i])
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def f(s, t, x):
  if s==H:
    return g(s, t-1)
  
  if AB[s][0]<=t<=AB[s][1]:
    if AB[s][1]==W:
      return g(s, t-1)
    else:
      ans[s+1]=min(ans[s+1], x+AB[s][1]-t+2)
      return f(s+1, AB[s][1]+1, x+AB[s][1]-t+2)
  else:
    ans[s+1]=min(ans[s+1], x+1)
    return f(s+1, t ,x+1)
  
def g(s, t):
  if s==0:
    return t
  if AB[s-1][0]<=t<=AB[s-1][1]:
    return g(s-1, AB[s-1][0]-1)
  else:
    return g(s-1, t)

H, W=map(int, input().split())
AB=[list(map(int, input().split())) for i in range(H)]
ans=[10**6]*(H+1)
t=W
while t>0:
  t=f(0, t, t-1)
  
ans=[ans[i] if ans[i]!=10**6 else -1 for i in range(1, H+1)]
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
ab=[]
for _ in range(h):
    i,j=map(int,input().split())
    ab.append((i,j))
now = 1
n_sum = 0
for (i,j) in ab:
    if now < i:
        p=now
        n_sum += 1
    elif i<=now<=j:
        p = j+1
        n_sum += (j+1) - now + 1
        now = j+1
    elif j<now:
        p = now
        n_sum += 1
    if p>w:
        print(-1)
    else:
        print(n_sum)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

H, W = map(int, input().split())
cur = 1
ans = 0
ok = True
for i in range(H):
    a, b = map(int, input().split())
    if a <= cur and cur <= b:
        ans += b - cur + 1
        cur = b + 1
        if cur > W:
            ok = False
    ans += 1
    if not ok:
        print(-1)
        continue
    else:
        print(ans)

Submission status: Wrong Answer

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

cnt = 0
now = 1
for i in range(H):
  a, b = map(int, input().split())
  if i == 0:
    now = a - 1
  if now == -1:
    print(-1)
  elif (now < a) or (now > b):
    cnt += 1
    print(cnt)
  else:
    #print(a, b)
    if b >= W:
      now = -1
      print(-1)
    else:
      now2 = now
      now = b + 1
      cnt += b + 2 - now2
      print(cnt)
  #print("now", now)

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,w]
for i in range(h):
    AA,BB = map(int,input().split())
    A.append(AA)
    B.append(BB)
    if len(kouho) <= 500:
        if AA != 1:
            kouho.append(AA-1)
        if BB != w:
            kouho.append(BB+1)


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-start+i+1)

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

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
A.insert(0,0)
a,b = A[1]
if a==1 and b==W:
    for k in range(2,H+1):
        print(-1)
else:
    if a>1:
        x = 1
    else:
        x = b+1
    cnt = 1
    for k in range(2,H+1):
        print(cnt)
        if cnt>0:
            a,b = A[k]
            if a<=x<=b:
                cnt += b-x+2
                x = b+1
            else:
                cnt += 1
            if x>W:
                cnt = -1
    print(cnt)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ab = []
for _ in range(h):
    a, b = LI()
    a -= 1
    b -= 1
    ab.append([a, b])

que = deque([[0, 0, 0]])
ans = [inf] * h
while que:
    s, i, ret = que.popleft()
    a, b = ab[i]
    if a <= s <= b:
        if b + 1 < w:
            if i + 1 < h:
                que.append([b+1, i+1, ret + b - s + 2])
            ans[i] = min(ans[i], ret + b - s + 2)
    else:
        if i + 1 < h:
            que.appendleft([s, i+1, ret+1])
        ans[i] = min(ans[i], ret+1)


for i in ans:
    if i == inf:
        print(-1)
    else:
        print(i)

Submission status: Wrong Answer

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

ans = 0
w = 0
for h in range(H):
    a,b = AB[h]
    if a-1<=w<=b-1:
        ans += b-w
        w = b
    if w != W:
        ans += 1
    else:
        ans = -1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def f(s, t, x):
  if s==H:
    return -1
  
  if AB[s][0]<=t<=AB[s][1]:
    if AB[s][1]==W:
      return g(s, t-1)
    else:
      ans[s+1]=min(ans[s+1], x+AB[s][1]-t+2)
      return f(s+1, AB[s][1]+1, x+AB[s][1]-t+2)
  else:
    ans[s+1]=min(ans[s+1], x+1)
    return f(s+1, t ,x+1)
  
def g(s, t):
  if s==0:
    return t
  if AB[s-1][0]<=t<=AB[s-1][1]:
    return g(s-1, AB[s-1][0]-1)
  else:
    return g(s-1, t)

H, W=map(int, input().split())
AB=[list(map(int, input().split())) for i in range(H)]
ans=[10**6]*(H+1)
t=W
while t>0:
  t=f(0, t, t-1)
  
ans=[ans[i] if ans[i]!=10**6 else -1 for i in range(1, H+1)]
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
""" F
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(H, W):
    c = 0
    A, B = readIntegerSet(2)
    x = 0 if A > 0 else B + 1

    for k in range(H):
        if k > 0:
            A, B = readIntegerSet(2)
        if x > W-1:
            print(-1)
            continue
        if x >= A-1 and x <= B-1:
            x0 = x
            x = B
            if x > W-1:
                print(-1)
                continue
            c += (x - x0 + 1)
        else:
            c += 1
        print(c)



if __name__ == "__main__":
    _H, _W = readIntegerSet(2)

    main(_H, _W)

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,w]
for i in range(h):
    AA,BB = map(int,input().split())
    A.append(AA)
    B.append(BB)
    if len(kouho) <= 500:
        if AA != 1:
            kouho.append(AA-1)
        if BB != w:
            kouho.append(BB+1)


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.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 len(kouho) <= 300:
        if AA != 1:
            kouho.append(AA-1)
        if BB != w:
            kouho.append(BB+1)


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
import time
time0=time.time()
import random

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

start(1)
start(W)

while time.time()-time0<1.8:
    start(random.randint(1,W))
    
for a in ANS:
    if a!=1<<30:
        print(a)
    else:
        print(-1)

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<=200 == 0:
        if AA != 1:
            kouho.append(AA-1)
        if BB != w:
            kouho.append(BB+1)


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:
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)
  else:
    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)