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: Runtime Error

Solution code:
from bisect import bisect_left
from heapq import *

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

destination = list(range(W))
destination_to_cost = {i:0 for i in range(W)}

min_heapq = [0] * W
to_delete = []

for k in range(H):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    start_index = bisect_left(destination, A)
    index = start_index
    change_dest_flg = False
    while index < len(destination) and destination[index] <= B:
        change_dest_flg = True
        cost = destination_to_cost.pop(destination[index])
        heappush(to_delete, cost)
        if B != W - 1:
            if (B + 1 in destination_to_cost):
                if destination_to_cost[B+1] < (B - destination[index]) + cost:
                    heappush(to_delete, destination_to_cost[B+1])
                    destination_to_cost[B+1] = (B - destination[index]) + cost
                    heappush(min_heapq, (B - destination[index]) + cost)
            else:
                destination_to_cost[B+1] = (B - destination[index]) + cost
                heappush(min_heapq, (B - destination[index]) + cost)
        index += 1

    while to_delete and min_heapq[0] == to_delete[0]:
        heappop(min_heapq)
        heappop(to_delete)

    if change_dest_flg:
        if B != W - 1:
            destination[start_index:index] = [B + 1]
        else:
            del destination[start_index:index]
        
    
    if min_heapq:
        print(k + min_heapq[0])
    else:
        for _ in range(H - k):
            print(-1)
        exit()

Submission status: Runtime Error

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([[i, 0, 0] for i in range(w)])
ans = [inf] * h
while que:
    s, i, ret = que.popleft()
    a, b = ab[i]
    if a <= s <= b:
        if b + 1 < w:
            que.append([b+1, i+1, ret + b - s + 2])
            ans[i] = min(ans[i], ret + b - s + 2)
    else:
        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: Runtime Error

Solution code:
import sys

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


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

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

s = 0
for i in range(H):
    if X[i] == 0:
        s += 1
    else:
        break

if len(X) == 0:
    for i in range(H):
        print(i+1)
    exit()

m = max(X)

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

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

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

Submission status: Runtime Error

Solution code:
import sys

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


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

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

m = max(X)

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

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

Submission status: Runtime Error

Solution code:
from sys import exit

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

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

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

for v in res:
    print(v)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

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] * H

def dfs(x, y, cnt, cnt2):
    if ans[x] != -1:
        return
    if x != 0 and ans[x-1] == -1:
        ans[x-1] = cnt - cnt2
    if x == H:
        for i in ans:
            print(i)
        sys.exit()
    nx = x + 1
    ny = y
    if not A[x] <= ny <= B[x]:
        dfs(nx, ny, cnt + 1, cnt2)
    nx = x
    ny = y + 1
    if ny < W:
        if nx == 0:
            cnt2 += 1
        dfs(nx, ny, cnt + 1, cnt2)

dfs(0, 0, 0, 0)

for i in ans:
    print(i)

Submission status: Runtime Error

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

import sys
input=sys.stdin.readline

MAX=10**18
h,w=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(h)]
ans=[MAX]*h
for i in range(1,w+1):
    th=0
    tw=i
    start=i
    while tw<=w and th<=h:
        if arr[th][0]<=tw<=arr[th][1]:
            tw+=1
        else:
            ans[th]=min(ans[th],th+tw-start+1)
            th+=1
for val in ans:
    if val==MAX:
        print(-1)
    else:
        print(val)

Submission status: Runtime Error

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

import sys
input=sys.stdin.readline

MAX=10**18
h,w=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(h)]
ans=[MAX]*h
th=0
tw=1
while tw<=w:
    if arr[th][0]<=tw<=arr[th][1]:
        tw+=1
    else:
        ans[th]=(th+tw)
        th+=1
for val in ans:
    if val==MAX:
        print(-1)
    else:
        print(val)

Submission status: Runtime Error

Solution code:
4 4
2 4
1 1
2 3
2 4