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 = 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%300 == 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(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:
  if AB[0][0]<=t<=AB[0][1]:
    t-=1
  else:
    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:
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 = 1
for i in range(h):
    for j in range(now, w + 1):
        now = j -1
        if d[j] > i:
            break
    print(j + i + 1 if now < w else -1)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W = MAP()
AB = [LIST() for _ in range(H)]

for i in range(W):
	if AB[0][0] <= i <= AB[0][1]:
		continue
	else:
		start = i
		break
else:
	print(*[-1]*H, sep="\n")

ans = [1]
cnt = 1
loc = start
for i in range(1, H):
	if AB[i][0]-1 <= loc <= AB[i][1]-1:
		if AB[i][1] == W:
			ans += [-1]*(H-i)
			print(*ans, sep="\n")
			exit()
		else:
			cnt += AB[i][1]-loc+1
			ans.append(cnt)
			loc = AB[i][1]
	else:
		cnt += 1
		ans.append(cnt)

else:
	print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9
INF = 2 ** 31 - 1


def main():
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.buffer.readline

    H, W = map(int, input().split())
    N = W+1

    # N: 処理する区間の長さ

    LV = (N - 1).bit_length()
    N0 = 2 ** LV
    data = [INF] * (2 * N0)
    lazy = [None] * (2 * N0)

    # 伝搬対象の区間を求める
    def gindex(l, r):
        L = (l + N0) >> 1;
        R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1;
            R >>= 1

    # 遅延伝搬処理
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i - 1]
            if v is None:
                continue
            lazy[2 * i - 1] = data[2 * i - 1] = lazy[2 * i] = data[2 * i] = v
            lazy[i - 1] = None

    # 区間[l, r)をxで更新
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)

        L = N0 + l;
        R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R - 1] = data[R - 1] = x
            if L & 1:
                lazy[L - 1] = data[L - 1] = x
                L += 1
            L >>= 1;
            R >>= 1
        for i in ids:
            data[i - 1] = min(data[2 * i - 1], data[2 * i])

    # 区間[l, r)内の最小値を求める
    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l;
        R = N0 + r

        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R - 1])
            if L & 1:
                s = min(s, data[L - 1])
                L += 1
            L >>= 1;
            R >>= 1
        return s

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    for i in range(1, W+1):
        update(i, i+1, i)
    pq = [(0, 1)]
    #bit = Bit(W+1)
    for h in range(H):
        a, b = map(int, input().split())
        if a == 1:
            update(a, b+1, -INF)
        else:
            update(a, b+1, query(a-1, a))
        if b != W:
            pos = b+1
            origin = query(b+1, b+2)
            heappush(pq, (pos - origin, pos))
        #print(h, pq)
        while pq:
            cost, pos = pq[0]
            origin = pos - cost
            if query(pos, pos+1) != origin:
                heappop(pq)
            else:
                print(cost + h + 1)
                break
        if not pq:
            print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    H, W = map(int, input().split())
    ans = 0
    now = 0
    
    for i in range(H):
        a, b = map(lambda x: int(x)-1, input().split())
        # print(a,b,now)
        if a <= now <= b:
            ans += b+1-now
            now = b+1
            # print(ans,now)
        if now >= W:
            print(-1)
        else:
            ans += 1
            print(ans)

if __name__ == "__main__":
    main()

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)
        continue
    if (a[i] <= pos[1]) and (pos[1] <= b[i]):
        diff = b[i] - pos[1] + 1
        pos[1] += diff
        num += diff
    pos[0] += 1
    num += 1
    if pos[1] >= W:
        num = -1
    print(num)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
ans = 0
x = 1

for i in range(h):
  a, b = map(int, input().split())
  if a <= x <= b:
    ans += b - x + 2
    x = b + 1
  else:
    ans += 1
  if x > w:
    print(-1)
  else:
    print(ans)

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)
    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 ans:
    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))
            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:
H, W = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(H)]

now = 0 # 現在のy座標
ans = 0 # 操作回数
for h in range(H):
  #print(X[h][0]-1 , now,  X[h][1]-1)
  if X[h][0]-1 <= now <= X[h][1]:
    ans += X[h][1] - now
    now = X[h][1]
  ans += 1
  print(ans if now <= W-1 else -1)

Submission status: Wrong Answer

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

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

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

c = 0
flg = False
Am = 10**5
for i in range(H):
    Am = min(Am, A[i])
    if Am <= ST[i] <= B[i]:
        if B[i] == W:
            flg = True
        c = i+B[i]-ST[i]+2
    else:
        c = i+1
    if flg:
        print(-1)
    else:
        print(c)

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)
    if 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:
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 + 1:
        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 + 1 - destination[index]) + cost:
                    heappush(to_delete, destination_to_cost[B+1])
                    destination_to_cost[B+1] = (B + 1 - destination[index]) + cost
                    heappush(min_heapq, (B + 1 - destination[index]) + cost)
            else:
                destination_to_cost[B+1] = (B + 1 - destination[index]) + cost
                heappush(min_heapq, (B + 1 - 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 = destination[:start_index] + [B+1] + destination[index:]
        else:
            del destination[start_index:index]
        
    
    if min_heapq:
        print(k + min_heapq[0] + 1)
    else:
        for _ in range(H - k):
            print(-1)
        exit()

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) == 0:
      ok = mid
    else:
      ng = mid
  ans = i+c-ok+1
  print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

h , w = 0, 1
ret = 0
while h<H:
    if AB[h][0] <= w <= AB[h][1]:
        ret += AB[h][1] - w + 1
        w = AB[h][1] + 1
    ret += 1
    if w <= W:
        print(ret)
    else:
        print(-1)
    h += 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
            if pos[1] >= W:
                num = -1
                break
        pos[0] += 1
        num += 1
    print(num)

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


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:
# -*- 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]:
            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:
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
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

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)