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()

class SegmentTreeDual():
    def __init__(self, init, unitX, unitA, g, h):
        self.g = g # (X, A, size) -> X
        self.h = h # (A, A) -> A
        self.unitA = unitA
        if type(init) == int:
            self.n = init
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
    
    def debug(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")
class SegmentTree():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f # (X, X) -> X
        self.g = g # (X, A, size) -> X
        self.h = h # (A, A) -> A
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def update(self, i, x):
        i += self.n
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
            i >>= 1
    
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def calc_above(self, i):
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2|1))
            i >>= 1
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getrange(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        
        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
        
        self.calc_above(l0)
        self.calc_above(r0)
    
    def debug(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")

H, W = map(int, input().split())
inf = 1 << 18
g = lambda x, a, s: x if a == -1 else a
h = lambda a, b: a if b == -1 else b
unitA = -1
unitX = inf
N = W + 2
st1 = SegmentTreeDual([-inf] + [i for i in range(1, W + 1)] + [-inf] * (N - W - 1), unitX, unitA, g, h)

f2 = lambda x, y: min(x, y)
g2 = lambda x, a, s: x if a == -1 else a
h2 = lambda a, b: a if b == -1 else b
unitX = inf
unitA = -1
st2 = SegmentTree([inf] + [0 for i in range(1, W + 1)] + [inf] * (N - W - 1), unitX, unitA, f2, g2, h2)
for i in range(H):
    a, b = map(int, input().split())
    b += 1
    l = st1.getvalue(a-1)
    st2.operate_range(a, b, a - l)
    r = st1.getvalue(b)
    st2.operate_range(b, b+1, b - r)
    st1.operate_range(a, b, l)
    print(st2.X[1] + i + 1 if st2.X[1] < inf else -1)

Submission status: Wrong Answer

Solution code:
# import numpy as np

H,W = list(map(int,input().split()))
A=[0 for _ in range(H)]
B=[0 for _ in range(H)]
LAns=[-1 for _ in range(H)]
RAns=[-1 for _ in range(H)]
for h in range(H):
	a,b=map(int,input().split())
	A[h] = a-1
	B[h] = b-1


# 左から行った場合の最小値を求める
leftAns = 0
curMin = W-1
rightMove = 0
curPos = 0	# 途中でそうではなかったことになるが、一番左から始める
for h in range(H):
	if curPos < A[h]:
		# 左が通れる限り、常にそこを下へ通すので右への移動はなし
		# LAns[h] = h + rightMove
		pass
	else:	# 今回値のせいで左が通れない場合
		if A[h] <= curPos:
			# print(h,A[h],curPos)
			if B[h] == W-1:
				# こうなったらこの後全部ダメ
				break

			if B[h] < curPos:
				# 右を通せた
				pass
			elif B[h] < curMin-1:
				# 今までの最小値-1が、B[h]よりも大きければ、
				# 最初がB[h]+1だったことにすれば良いので、右への移動はなし
				pass
			else:
				# 今までの最小値が、B[h]以下でも、
				# 最初がそこだったことにするが、
				# 右への移動は必要になる
				if 0 < curMin:
					curPos = curMin - 1
				rightMove += (B[h]+1)-(curPos)
				# print("min",(B[h]+1), curPos)


			# 必要あれば右まで移動
			curPos=max(curPos,B[h]+1)

	LAns[h] = h+1 + rightMove
	# print("curMin",curMin,A[h])
	curMin = min( curMin, A[h] )



# 右から行った場合の最小値を求める
rightAns = 0
curMin = W-1
rightMove = 0
curPos = B[0]+1	# 途中でそうではなかったことになるが、B[0]+1から始めたことにする
for h in range(H):
	if W <= curPos:
		# print("dead",h,curPos)
		break
	elif B[h] < curPos:
		# 右が通れる限り、常にそこを通す
		pass
	else:	# 今回値のせいで右が通れない場合
		if curPos < A[h]:
			# 左なら通れた
			pass
		elif B[h] == W-1:
			# 左が通れないのに右も通れない
			# こうなったらこの後全部ダメ
			break
		elif B[h] < curMin:
			# 左は通れなかったが、右移動でいける
			# 今までの最小値-1が、B[h]よりも大きければ、
			# 最初がB[h]+1だったことにすれば良いので、この行で右へ移動はしない
			# 現在地移動
			curPos=B[h]+1
		else:
			# 左は通れなかったが、右移動でいける
			# 今までの最小値が、B[h]以下でも、
			# 最初がそこだったことにするが、
			# この行で右への移動は必要になる
			if 0 < curMin:
				curPos = curMin - 1
			rightMove += (B[h]+1)-(curPos)
		
			# 現在地移動
			curPos=B[h]+1

	RAns[h] = h+1 + rightMove
	if curPos <= A[h]:
		curMin = min( curMin, A[h] )

# print(LAns)
# print(RAns)


for h in range(H):
	if RAns[h] == -1:
		if LAns[h] == -1:
			print(-1)
		else:
			print(LAns[h])
	elif LAns[h] == -1:
		print(RAns[h])
	else:
		print(min(LAns[h],RAns[h]))

Submission status: Wrong Answer

Solution code:
# import numpy as np

H,W = list(map(int,input().split()))
A=[0 for _ in range(H)]
B=[0 for _ in range(H)]
LAns=[-1 for _ in range(H)]
RAns=[-1 for _ in range(H)]
for h in range(H):
	a,b=map(int,input().split())
	A[h] = a-1
	B[h] = b-1


# 左から行った場合の最小値を求める
leftAns = 0
curMin = W-1
rightMove = 0
curPos = 0	# 途中でそうではなかったことになるが、一番左から始める
for h in range(H):
	if curPos < A[h]:
		# 左が通れる限り、常にそこを下へ通すので右への移動はなし
		# LAns[h] = h + rightMove
		pass
	else:	# 今回値のせいで左が通れない場合
		if A[h] <= curPos:
			# print(h,A[h],curPos)
			if B[h] == W-1:
				# こうなったらこの後全部ダメ
				break

			if B[h] < curPos:
				# 右を通せた
				pass
			elif B[h] < curMin-1:
				# 今までの最小値-1が、B[h]よりも大きければ、
				# 最初がB[h]+1だったことにすれば良いので、右への移動はなし
				pass
			else:
				# 今までの最小値が、B[h]以下でも、
				# 最初がそこだったことにするが、
				# 右への移動は必要になる
				if 0 < curMin:
					curPos = curMin - 1
				rightMove += (B[h]+1)-(curPos)
				print("min",(B[h]+1), curPos)


			# 必要あれば右まで移動
			curPos=max(curPos,B[h]+1)

	LAns[h] = h+1 + rightMove
	# print("curMin",curMin,A[h])
	curMin = min( curMin, A[h] )



# 右から行った場合の最小値を求める
rightAns = 0
curMin = W-1
rightMove = 0
curPos = B[0]+1	# 途中でそうではなかったことになるが、B[0]+1から始めたことにする
for h in range(H):
	if W <= curPos:
		# print("dead",h,curPos)
		break
	elif B[h] < curPos:
		# 右が通れる限り、常にそこを通す
		pass
	else:	# 今回値のせいで右が通れない場合
		if curPos < A[h]:
			# 左なら通れた
			pass
		elif B[h] == W-1:
			# 左が通れないのに右も通れない
			# こうなったらこの後全部ダメ
			break
		elif B[h] < curMin:
			# 左は通れなかったが、右移動でいける
			# 今までの最小値-1が、B[h]よりも大きければ、
			# 最初がB[h]+1だったことにすれば良いので、この行で右へ移動はしない
			# 現在地移動
			curPos=B[h]+1
		else:
			# 左は通れなかったが、右移動でいける
			# 今までの最小値が、B[h]以下でも、
			# 最初がそこだったことにするが、
			# この行で右への移動は必要になる
			if 0 < curMin:
				curPos = curMin - 1
			rightMove += (B[h]+1)-(curPos)
		
			# 現在地移動
			curPos=B[h]+1

	RAns[h] = h+1 + rightMove
	if curPos <= A[h]:
		curMin = min( curMin, A[h] )

# print(LAns)
# print(RAns)


for h in range(H):
	if RAns[h] == -1:
		if LAns[h] == -1:
			print(-1)
		else:
			print(LAns[h])
	elif LAns[h] == -1:
		print(RAns[h])
	else:
		print(min(LAns[h],RAns[h]))

Submission status: Wrong Answer

Solution code:
# import numpy as np

H,W = list(map(int,input().split()))
A=[0 for _ in range(H)]
B=[0 for _ in range(H)]
LAns=[-1 for _ in range(H)]
RAns=[-1 for _ in range(H)]
for h in range(H):
	a,b=map(int,input().split())
	A[h] = a-1
	B[h] = b-1


# 左から行った場合の最小値を求める
leftAns = 0
curMin = A[0]
rightMove = 0
curPos = 0	# 途中でそうではなかったことになるが、一番左から始める
for h in range(H):
	if curPos < A[h]:
		# 左が通れる限り、常にそこを下へ通すので右への移動はなし
		# LAns[h] = h + rightMove
		pass
	else:	# 今回値のせいで左が通れない場合
		if A[h] <= curPos:
			# print(h,A[h],curPos)
			if B[h] == W-1:
				# こうなったらこの後全部ダメ
				break

			if B[h] < curMin-1:
				# 今までの最小値-1が、B[h]よりも大きければ、
				# 最初がB[h]+1だったことにすれば良いので、右への移動はなし
				pass
			else:
				# 今までの最小値が、B[h]以下でも、
				# 最初がそこだったことにするが、
				# 右への移動は必要になる
				if 0 < curMin:
					curPos = curMin - 1
				rightMove += (B[h]+1)-(curPos)


			# 右まで移動は確実
			curPos=B[h]+1

	LAns[h] = h+1 + rightMove
	# print("curMin",curMin,A[h])
	curMin = min( curMin, A[h] )



# 右から行った場合の最小値を求める
rightAns = 0
curMin = W-1
rightMove = 0
curPos = B[0]+1	# 途中でそうではなかったことになるが、B[0]+1から始めたことにする
for h in range(H):
	if W <= curPos:
		# print("dead",h,curPos)
		break
	elif B[h] < curPos:
		# 右が通れる限り、常にそこを通す
		pass
	else:	# 今回値のせいで右が通れない場合
		if curPos < A[h]:
			# 左なら通れた
			pass
		elif B[h] == W-1:
			# 左が通れないのに右も通れない
			# こうなったらこの後全部ダメ
			break
		elif B[h] < curMin-1:
			# 左は通れなかったが、右移動でいける
			# 今までの最小値-1が、B[h]よりも大きければ、
			# 最初がB[h]+1だったことにすれば良いので、この行で右へ移動はしない
			# 現在地移動
			curPos=B[h]+1
		else:
			# 左は通れなかったが、右移動でいける
			# 今までの最小値が、B[h]以下でも、
			# 最初がそこだったことにするが、
			# この行で右への移動は必要になる
			if 0 < curMin:
				curPos = curMin - 1
			rightMove += (B[h]+1)-(curPos)
		
			# 現在地移動
			curPos=B[h]+1

	RAns[h] = h+1 + rightMove
	if curPos <= A[h]:
		curMin = min( curMin, A[h] )

# print(RAns)


for h in range(H):
	if RAns[h] == -1:
		if LAns[h] == -1:
			print(-1)
		else:
			print(LAns[h])
	elif LAns[h] == -1:
		print(RAns[h])
	else:
		print(min(LAns[h],RAns[h]))

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
ran=[[j-1 for j in list(map(int,input().split()))] for i in range(h)]
cand=[]
if ran[0][0]>1:
    cand.append(0)
    cand.append(ran[0][0]-1)
elif ran[0][0]==1:
    cand.append(ran[0][0]-1)
if ran[0][1]<w-2:
    cand.append(w-1)
    cand.append(ran[0][1]+1)
elif ran[0][1]==w-2:
    cand.append(ran[0][1]+1)
dp=[[[-1,-1] for j in range(h+1)] for i in range(len(cand))]
ans=[-1]*h
for i in range(len(cand)):
    dp[i][0]=[cand[i],0]
    for j in range(h):
        if dp[i][j][0]<ran[j][0]:
            if ran[j][0]==0:
                break
            else:
                dp[i][j+1]=[dp[i][j][0],dp[i][j][1]+1]
        elif dp[i][j][0]<=ran[j][1]:
            if ran[j][1]==w-1:
                break
            else:
                dp[i][j+1]=[ran[j][1]+1,dp[i][j][1]+(ran[j][1]-dp[i][j][0]+1)+1]
        else:
            if ran[j][1]==w-1:
                break
            else:
                dp[i][j+1]=[dp[i][j][0],dp[i][j][1]+1]
    for j in range(h):
        if dp[i][j+1][1]!=-1:
            if ans[j]!=-1:
                ans[j]=min(ans[j],dp[i][j+1][1])
            else:
                ans[j]=dp[i][j+1][1]
for i in range(h):
    print(ans[i])

Submission status: Wrong Answer

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

MAX=10**19

spre=0
for h in range(H+1):
    if h<H:
        a,b=[int(e)-1 for e in input().split()]
    else:
        a=b=0
    if h!=0:
        if spre==W:
            print(-1)
            continue
        print(h+spre)
    if a<=spre:
        spre=max(b+1,spre)
    #print("  ",h,spre)

Submission status: Wrong Answer

Solution code:
def pri(c):
    print(*c, sep="\n")
def inrange(x, a):

    return a[0] <= x and x <= a[1]
[h, w] = map(int, input().split())
rng = [[0, 0]]
for i in range(1, h+1):
    tmp = list(map(int, input().split()))
    rng.append(tmp)
# pri(rng)
# path = 0
pos = 1
for k in range(1, h+1):
    while pos <= w:
        if inrange(pos, rng[k]):
            pos += 1
        else:
            break
    if(pos > w):
        print(-1)
    else:
        print(k+pos-1)
# print(inrange(2,rng[2]))
# print(inrange(1,rng[2]))

Submission status: Wrong Answer

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    
    h, w = mi()
    L = [lmi_0() for _ in range(h)]

    
    def solve(h, w, L):
        cnt = 0
        now = 0
        move = []
        for i in range(h):
            # i 行目にたどりつくコストをメモ
            move.append(cnt)
            a, b = L[i]
            if a <= now <= b:
                cnt += (b + 1 - now)
                now = b + 1
            if now == w:
                return move
            cnt += 1    # 1 段降りる
        move.append(cnt)
        return move

    

    cost = solve(h, w, L)
    last = len(cost)
    for i in range(1, h + 1):
        if i + 1 > last:
            print(-1)
        else:
            print(cost[i])



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,w]
used = [True]*(w+1)
used[1] = False
used[w] = False

for i in range(h):
    AA,BB = map(int,input().split())
    A.append(AA)
    B.append(BB)
    if h <= 500:
        if len(kouho) <= 500:
            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
    else:
        if i%100 == 0 and len(kouho) <= 500:
            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
AA,BB = A[-1],B[-1]
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)
        else:
            break
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)]

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

inf = 10 ** 19

ans = [inf] * h
for i in range(1, w + 1):
  pos = i
  steps = 0
  downable = True
  for itr, (a, b) in enumerate(AB):
    if not downable:
      continue
    else:
      if pos < a or b < pos:
        steps += 1
        if steps >= ans[itr]:
          continue
        else:
          ans[itr] = steps
      elif a <= pos <= b:
        steps += b - pos + 2 # 右へ：b - pos + 1、下へ1
        pos = b + 1
        if b >= w:
          continue
          downable = False
        else:
          if steps >= ans[itr]:
            continue
          else:
            ans[itr] = steps

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

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)
used[1] = False
used[w] = False

for i in range(h):
    AA,BB = map(int,input().split())
    A.append(AA)
    B.append(BB)
    if h <= 500:
        if len(kouho) <= 500:
            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
    else:
        if i%100 == 0 and len(kouho) <= 450:
            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
AA,BB = A[-1],B[-1]
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

print(kouho)

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)
        else:
            break
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())
ran=[[j-1 for j in list(map(int,input().split()))] for i in range(h)]
cand=[]
if ran[0][0]>1:
    cand.append(0)
    cand.append(ran[0][0]-1)
elif ran[0][0]==1:
    cand.append(ran[0][0]-1)
if ran[0][1]<w-2:
    cand.append(w-1)
    cand.append(ran[0][1]+1)
elif ran[0][1]==w-2:
    cand.append(ran[0][1]+1)
dp=[[[-1,-1] for j in range(h+1)] for i in range(len(cand))]
ans=[-1]*h
for i in range(len(cand)):
    dp[i][0]=[cand[i],0]
    for j in range(h):
        if dp[i][j][0]<ran[j][0]:
            if ran[j][0]==0:
                break
            else:
                dp[i][j+1]=[dp[i][j][0],dp[i][j][1]+1]
        elif dp[i][j][0]<=ran[j][1]:
            if ran[j][1]==w-1:
                break
            else:
                dp[i][j+1]=[ran[j][1]+1,dp[i][j][1]+ran[j][1]-dp[i][j][0]+2]
        else:
            dp[i][j+1]=[dp[i][j][0],dp[i][j][1]+1]
    for j in range(h):
        if dp[i][j+1][1]!=-1:
            if ans[j]!=-1:
                ans[j]=min(ans[j],dp[i][j+1][1])
            else:
                ans[j]=dp[i][j+1][1]
for i in range(h):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
c = 1
B = [0]*(w+3)
def add(i, x):
  while i <= w+2:
    B[i] += x
    i += i&-i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i&-i
  return res
for i in range(h):
  if c > w:
    print(-1)
    continue
  a, b = map(int, input().split())
  add(a, 1)
  add(b+1, -1)
  if a <= c <= b:
    c = b+1
  if c > w:
    print(-1)
    continue
  ans = i+c
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    obstacle = [list(map(int, input().split())) for _ in range(H)]
    y = 1
    t = 0
    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
    i_max = i
    ans = [float('inf')] * H
    for y in range(W, 0, -1):
        t = 0
        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] = min(ans[i], t)
        if i == i_max:
            break

    for i in range(H):
        if type(ans[i]) is float:
            print(-1)
        else:
            print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

dp = [0] * (W)
predp = [0] * (W)
pre = 0
now = 1
for i in range(H):
    a,b = AB[i]
    j = False
    if a <= now:
        now = b+1
    if now > W:
        print(-1)
    else:
        pre += max(0, now-a) + 1
        print(pre)

Submission status: Wrong Answer

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

A = W+1
identity = -(1<<62)
sqrtA = 500
n_buckets = A // sqrtA + 1
Data = [0] * (n_buckets * sqrtA)
Data[0] = 1<<30
Bucket_min = [0] * n_buckets
Lazy = [identity] * n_buckets

def eval_data(k):
    if Lazy[k] != identity:
        l, r = k*sqrtA, (k+1) * sqrtA
        for i in range(l, r):
            Data[i] = i-Lazy[k]
        Lazy[k] = identity

def update(s, t, x):
    for k in range(s//sqrtA, (t-1)//sqrtA+1):
        l, r = k*sqrtA, (k+1)*sqrtA
        if s <= l and r <= t:
            Bucket_min[k] = l - x
            Lazy[k] = x
        else:
            eval_data(k)
            for i in range(max(l,s), min(r,t)):
                Data[i] = i-x
                Bucket_min[k] = min(Bucket_min[k], i-x)

def get_min(s, t):
    res = 1 << 62
    bl, br = s//sqrtA+1, t//sqrtA
    if bl > br:
        eval_data(br)
        return min(Data[s:t])
    if bl < br:
        res = min(Bucket_min[bl:br])
    ll, rr = bl*sqrtA, br*sqrtA
    if s < ll:
        eval_data(bl - 1)
        mi = min(Data[s:ll])
        if res > mi:
            res = mi
    if rr < t:
        eval_data(br)
        mi = min(Data[rr:t])
        if res > mi:
            res = mi
    return res

Ans = []
for i, (a, b) in enumerate(AB, 1):
    update(a, b+1, a-1-get_min(a-1, a))
    ans = get_min(1, W+1)
    Ans.append(ans + i if ans < 1<<25 else -1)
print("\n".join(map(str, Ans)))

Submission status: Wrong Answer

Solution code:
# import numpy as np

H,W = list(map(int,input().split()))
A=[0 for _ in range(H)]
B=[0 for _ in range(H)]
LAns=[-1 for _ in range(H)]
RAns=[-1 for _ in range(H)]
for h in range(H):
	a,b=map(int,input().split())
	A[h] = a-1
	B[h] = b-1


# 左から行った場合の最小値を求める
leftAns = 0
curMin = A[0]
rightMove = 0
curPos = 0	# 途中でそうではなかったことになるが、一番左から始める
for h in range(H):
	if curPos < A[h]:
		# 左が通れる限り、常にそこを下へ通すので右への移動はなし
		# LAns[h] = h + rightMove
		pass
	else:	# 今回値のせいで左が通れない場合
		if A[h] <= curPos:
			# print(h,A[h],curPos)
			if B[h] == W-1:
				# こうなったらこの後全部ダメ
				break

			if B[h] < curMin-1:
				# 今までの最小値-1が、B[h]よりも大きければ、
				# 最初がB[h]+1だったことにすれば良いので、右への移動はなし
				pass
			else:
				# 今までの最小値が、B[h]以下でも、
				# 最初がそこだったことにするが、
				# 右への移動は必要になる
				if 0 < curMin:
					curPos = curMin - 1
				rightMove += (B[h]+1)-(curPos)


			# 右まで移動は確実
			curPos=B[h]+1

	LAns[h] = h+1 + rightMove
	# print("curMin",curMin,A[h])
	curMin = min( curMin, A[h] )



# 右から行った場合の最小値を求める
rightAns = 0
curMax = B[h]
rightMove = 0
curPos = B[0]	# 途中でそうではなかったことになるが、B[0]から始めたことにする
for h in range(H):
	if B[h] == W-1:
		# こうなったらこの後全部ダメ
		break
	elif curMax < B[h]:
		# 右が通れる限り、常にそこを通す
		pass
	else:	# 今回値のせいで右が通れない場合
		if curPos <= B[h]:
			# 一番右まで行ってないので、最初がそこだったことにすれば良い
			# 右まで移動は確実
			curPos=B[h]+1

	RAns[h] = h + 1
	curMin = min( curMin, A[h] )




for h in range(H):
	if RAns[h] == -1:
		if LAns[h] == -1:
			print(-1)
		else:
			print(LAns[h])
	elif LAns[h] == -1:
		print(RAns[h])
	else:
		print(min(LAns[h],RAns[h]))