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:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

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

cost = [0 for i in range(W)]
anss = [0 for i in range(H)]
for h in range(H+1):
    if h == H:
        break
    a, b = ab[h]
    for w in range(W):
        if a == 0:
            cost[0] = mod
        if a > 0:
            if a <= w <= b:
                cost[w] = cost[a - 1] + w - a + 2
            else:
                cost[w] = cost[w] + 1
    # print(cost)
    anss[h] = min(cost)

for h in range(H):
    if anss[h] == mod:
        print(-1)
    else:
        print(anss[h])

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:
      ans[itr] = min(ans[itr], inf)
    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:
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]:
            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:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
IINF=10**17
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W=map(int,input().split())
A,B=[0]*H,[0]*H
for i in range(H):
    A[i],B[i]=map(int1,input().split())

dp=[[INF]*2 for _ in range(H+1)]
dp[0][0]=dp[0][1]=1
l=[A[i]-1,B[i]+1]
if l[0]<-1:
    dp[0][0]=INF
if l[1]>=W:
    dp[0][1]=INF
for i in range(H-1):
    for k in range(2):
        if dp[i][k]<IINF:
            if dp[i][k]<A[i+1]:
                dp[i+1][k]=dp[i][k]+1
            elif B[i+1]<W-1:
                dp[i+1][k]=B[i+1]+1-l[k]+i+2
for i in range(H):
    ans=min(dp[i])
    print(ans if ans!=INF else -1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    cur = 0
    ans = 0
    for h in range(H):
        if cur >= W:
            print(-1)
        ans += 1
        a, b = [int(x)-1 for x in input().strip().split()]
        if cur < a or cur > b:
            print(ans)
        else:
            ans += b - cur + 1
            cur = b+1
            if cur >= W:
                print(-1)
                continue
            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, r_left = 1, W
rmax = 0
for h in range(1, H+1):
    a, b = mapint()
    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 and r_left==W:
        if b!=W:
            dp[1][h] = dp[1][h-1] + 1
            rmax = max(b, rmax)
        else:
            if rmax>=a-1:
                break
            else:
                r_left = a-1
    else:
        dp[0][h] = min(dp[0][h], dp[1][h-1]+(b-a+2))

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 = 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
  ok = 1
  ng = c+1
  while ng - ok > 1:
    mid = (ok+ng) // 2
    if acc(mid) - acc(mid-1) < i:
      ok = mid
    else:
      ng = mid
  ans = i+c-ok+1
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############


H,N = IL()
raw_data = ILL(H)
# N: 処理する区間の長さ

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

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]
  
update(1,N+1,(0,H))

magarikado = [None for i in range(H)]
for i in range(H)[::-1]:
  update(raw_data[i][0]-1,raw_data[i][1],(H-i,i))
  magarikado[i] = query(raw_data[i][1])
  
#print(magarikado)


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

        if L & 1:
            best[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query2(k):
    k += N1-1
    s = INF
    while k >= 0:
        if best[k]:
          if s[1]>best[k][1]:
            s = max(s, best[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query2(k):
    return _query2(k)[1]

wall = DD(int)

update2(0,1,(0,0))

t = 0
for i in range(N):
  nowx = i
  nowy = query(i)
  d = 0
  t += 1
  update2(0,nowy+1,(t,d))
  #print(i,0,nowy+1,(t,d))
  if wall[nowy]: continue
  wall[nowy] = 1
  while nowx < N and nowy < H:
    d += raw_data[nowy][1]-nowx
    nowx = raw_data[nowy][1]
    if nowx == N: break
    newy = magarikado[nowy]
    if wall[newy]: break
    wall[newy] = 1
    t += 1
    update2(nowy+1,newy+1,(t,d))
    #print(i,nowy+1,newy+1,(t,d))
    nowy = newy
 
    
#print(query2(5))
for i in range(H):
  tmp = query2(i+1)
  if tmp == 2**31-1:
    print(-1)
  else:
    print(tmp + i + 1)

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:
      ans[itr] = min(ans[itr], inf)
    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
        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:
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]:
            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:
            ans[j]=min(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())

notdown=[]


for _ in range(h):
    l,r=map(int,input().split())
    notdown.append((l-1,r-1))

dp=[0]*w


ans=[]
for k in range(h):
    tmp="INF"

    for j in range(w):
        if j==0:
            #上から降りてこれない場合
            if notdown[k][0]<=j and j<=notdown[k][1]:
                dp[j]=-1

            #上から降りてこれる場合
            else:
                #上から降りてこれるけど、上のマスに到達されている場合
                if dp[j]!=-1:
                    dp[j]+=1
                    if tmp=="INF":
                        tmp=dp[j]
                    else:
                        tmp=min(tmp,dp[j]+1)
        else:
            #上から降りてこれない
            if notdown[k][0]<=j and j<=notdown[k][1]:
                #左からも来れない
                if dp[j-1]==-1:
                    continue
                #左からはこれる
                else:
                    dp[j]=dp[j-1]+1
                    if tmp=="INF":
                        tmp=dp[j]
                    else:
                        tmp=min(tmp,dp[j]+1)
            #上から降りてこれる
            else:
                #左からこれない
                if dp[j-1]==-1:
                    if dp[j]!=-1:     
                        dp[j]=dp[j-1]+1
                        if tmp=="INF":
                            tmp=dp[j]
                        else:
                            tmp=min(tmp,dp[j]+1)
                #左からこれる
                else:
                    if dp[j]!=-1:
                        dp[j]=min(dp[j-1]+1,dp[j]+1)
                        if tmp=="INF":
                            tmp=dp[j]
                        else:
                            tmp=min(tmp,dp[j]+1)


                    



    
    if tmp=="INF":
        ans.append(-1)
    else:
        ans.append(tmp)
            


    
for item in ans:
    print(item)
#for k in range(h):

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 = 50
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)
        print(s, t, Data[s:t])
        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):
    ans = get_min(1, W+1)
    print(ans)
    Ans.append(ans + i)
    print(a-1)
    update(a, b+1, a-1-get_min(a-1, a))
    print(Data)
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]))

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 ANS[i]<=SCORE and (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 = [[int(i) - 1 for i in input().split()] for _ in range(H)]

ret = [float('inf')] * H
last = [-1] * H
for dx in range(W) :
  x = dx
  for y in range(H) :
    if AB[y][0] <= x <= AB[y][1] :
      if AB[y][1] == W - 1 :
        break
      else :
        x = AB[y][1] + 1
    if last[y] == x :
      break
    last[y] = x
    ret[y] = min(ret[y], x - dx + 1 + y)
    
for y in range(H) :
  if ret[y] == float('inf') :
    print(-1)
  else :
    print(ret[y])

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

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
        else:
            break
        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
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 = [-1 for _ in range(H * W)]
ans2 = [INF] * H
 
def dfs(x, y, cnt, cnt2):
    if x != 0 and ans[(x-1) * W + y] != -1 and ans[(x-1) * W + y] <= cnt - cnt2:
        return
    if x != 0 and (ans[(x-1) * W + y] == -1 or ans[(x-1) * W + y] > cnt - cnt2):
        ans[(x-1) * W + y] = cnt - cnt2
        ans2[x-1] = min(ans2[x-1], cnt - cnt2)
    if x == H:
        for i in ans2:
            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)
    if y < B[x] and 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 ans2:
    if i == INF:
        print(-1)
    else:
        print(i)

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))
            erase.add((pos-fr,fr))
            exist[fr]=False
            BT.delete(val)
        else:
            if pos==b+1 and erasemax[1]!=-1 and b+1<=W and erasemax[1]>=fr:
                BT.delete(val)
                exist[fr]=False
                erase.add((pos-fr,fr))

                BT.append(((b+1)<<20)+erasemax[1])
                erase.add(erasemax)
                heapq.heappush(que,(b+1-erasemax[1],erasemax[1]))
                exist[erasemax[1]]=True
            elif 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
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	h,w=MI()
	a,b=MI()
	now=a-1
	ans=1
	print(ans)
	for i in range(h-1):
		a,b=MI()
		if ans==-1:
			print(-1)
		else:
			ans+=1
			if a<=now<=b:
				if b+1>w:
					ans=-1
					now=w+1
				else:
					ans+=b+1-now
					now=b+1
			print(ans)




if __name__ == "__main__":
	main()

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


import numpy as np
from numba import njit, b1, i4, i8, f8

@njit((i8,i8,i8[:,:]), cache=True)
def main(h,w,ab):
    dp = np.zeros((h,), dtype=np.int64)
    v = 1
    i = 0
    for i in range(h):
        a,b = ab[i]
        if a<=v<=b:
            v = b+1
        dp[i] = v
        i += 1
    dp2 = np.zeros((h,), dtype=np.int64)
    done = np.zeros((h,), dtype=np.int32)
    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
    ans = np.zeros((h,), dtype=np.int64)
    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])
            ans[i] = min((i+1)+(dp[i]-1), (i+1)+(w-dp2[i]))
    return ans
h,w = map(int, input().split())
ab = np.array([tuple(map(int, input().split())) for _ in range(h)], dtype=np.int64)
ans = main(h,w,ab)
write("\n".join(map(str, ans)))