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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


h,w = map(int,readline().split())
data = list(map(int,read().split()))

ans = []
left = 1

it = iter(data)
for i,a,b in zip(range(1,h+1), it,it):
    if(left==w+1):
        ans.append(-1)
        continue
    if(left>=a):
        left = b+1
    if(left==w+1):
        ans.append(-1)
        continue

    ans.append(i+left-1)
    # print(i,left,i+left-1)

print('\n'.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    h,w = map(int,ipt().split())
    mi = 1
    for i in range(h):
        a,b = map(int,ipt().split())
        if a <= mi <= b:
            mi = b+1
        if mi == w+1:
            print(-1)
        else:
            print(mi+i)

    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

l = [tuple(map(int, input().split())) for _ in range(H)]
ans = 0
pos = 1
cost = 0
nr = False

for left, right in l:
    if left<=pos<=right:
        if pos<W and right<W:
            cost += (right+1)-pos
            pos = right+1
        else:
            nr = True
    cost += 1
    if nr:
        print(-1)
    else:
        print(cost)

Submission status: Wrong Answer

Solution code:
from sys import stdin
readline = stdin.readline

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

x = 0
c = 0
result = []
for _ in range(H):
    A, B = map(lambda x: int(x) - 1, readline().split())
    if x == W:
        result.append(-1)
    elif x < A or x > B:
        c += 1
        result.append(c)
    elif A <= x <= B:
        c += B - x + 2
        x = B + 1
        if x == W:
            result.append(-1)
        else:
            result.append(c)
print(*result, sep='\n')

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class LazySegTree:
        # Range add query
        def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)
            self.lazy = [0] * (self.N0 * 2)

        def _ascend(self, i):
            for _ in range(i.bit_length() - 1):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1]) + self.lazy[i]

        def _descend(self, idx):
            lv = idx.bit_length()
            for j in range(lv - 1, 0, -1):
                i = idx >> j
                x = self.lazy[i]
                if not x:
                    continue
                self.lazy[i] = 0
                self.lazy[i * 2] += x
                self.lazy[i * 2 + 1] += x
                self.data[i * 2] += x
                self.data[i * 2 + 1] += x

        # open interval [l, r)
        def add(self, l, r, x):
            l += self.N0 - 1
            r += self.N0 - 1
            l_ori = l
            r_ori = r
            while l < r:
                if l & 1:
                    self.data[l] += x
                    self.lazy[l] += x
                    l += 1
                if r & 1:
                    r -= 1
                    self.data[r] += x
                    self.lazy[r] += x
                l >>= 1
                r >>= 1
            self._ascend(l_ori // (l_ori & -l_ori))
            self._ascend(r_ori // (r_ori & -r_ori) - 1)

        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            ret = self.ident
            while l < r:
                if l & 1:
                    ret = self.segfunc(ret, self.data[l])
                    l += 1
                if r & 1:
                    ret = self.segfunc(self.data[r - 1], ret)
                    r -= 1
                l >>= 1
                r >>= 1
            return ret

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

    ST = LazySegTree([0] * W, initialize=True)
    left = 0
    for h in range(H):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if a <= left:
            left = b+1
        if left == W:
            print(-1)
            continue
        ST.add(a+1, b+2, 1)
        if ST.query(1, W+1) == 0:
            print(h+1)
        else:
            print(h+1 + left)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    h, w = map(int, input().split())
    
    ans = []
    now = 1
    for i in range(h):
        x, y = map(int, input().split())
        if now >= x:
            now = y+1
        
        
        if now == w+1:
            ans.append(-1)
            continue
        
        ans.append(i+now)
        
        
    for a in ans:
        print(a)
    
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

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

AB = []
best = []
now = 0
for i in range(H):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    if now == W-1:
        best.append(-1)
    if a <= now <= b:
        if b == W-1:
            best.append(-1)
        else:
            best.append(b+1)
            now = b+1
    else:
        best.append(now)

    AB.append((a-1,b-1))

for i in range(H):
    if best[i] == -1:
        print(-1)
    else:
        print(best[i]+i+1)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline

h, w = map(int, input().split())
cnt = [0] * (h)
now = 0
for i in range(h):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a <= now and now <= b:
        now = b + 1
    if now < w:
        cnt[i] = (i + 1) + now
    else:
        cnt[i] = -1
    # print(now)
delta = 0
if cnt[0] > 1:
    delta = cnt[0] - 1

for i in range(h):
    print(cnt[i] - delta)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

h, w = na()

pos = 0
for i in range(h):
    a, b = na()
    a -= 1
    b -= 1
    if a <= pos <= b:
        pos = b+1
    print(pos+i+1 if pos < w else -1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ans = [-1]*H
now = 1
cnt = 0
A,B = [0]*H,[0]*H
for i in range(H):
  A[i],B[i] = map(int, input().split())
for i in range(H):
  a,b = A[i],B[i]
  if now<a or now>b:
    cnt += 1
    ans[i] = cnt
  else:
    if b==W:
      ans[i]=-1
      break
    cnt += b+1-now+1
    ans[i] = cnt
    now = b+1
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

h,w = map(int,input().split())

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

Submission status: Wrong Answer

Solution code:
def main():
    h, w = map(int, input().split())
    ans = 0
    a, b = map(int, input().split())
    if 1 < a:
        p = 1
    else:
        p = b+1
    if p <= w:
        ans += 1
        print(1)
    else:
        p = w+1
        print(-1)
    for i in range(1, h):
        a, b = map(int, input().split())
        if p > w:
            print(-1)
            continue
        if p < a or p > b:
            ans += 1
        elif b == w:
            ans = -1
            p = w+1
        else:
            ans += b-p+2
            p = b+1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 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: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline
h, w = map(int, input().split())
cnt = [0] * (h)
now = 0
for i in range(h):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a <= now and now <= b:
        now = b + 1
    if now < w:
        cnt[i] = (i + 1) + now
    else:
        cnt[i] = -1
    # print(now)

print(*cnt, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline
h, w = map(int, input().split())
cnt = [0] * (h)
now = 0
for i in range(h):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a <= now and now <= b:
        now = b + 1
    if now < w:
        cnt[i] = (i + 1) + now
    else:
        cnt[i] = -1
    print(now)

print(*cnt, sep="\n")

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()
	now=1
	ans=0
	for i in range(h):
		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,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,w = m()
st = 1
count = 0
for i in range(h):
    a,b = m()
    if a <= st and st <= b:
        if st == w:
            print(-1)
        else:
            count += b-st + 1
            st = b+1
            count += 1
            print(count)
    else:
        count += 1
        print(count)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
x = 0
res = 0
for _ in range(H):
  if res == -1:
    print(-1)
    continue
  l, r = map(int, input().split())
  l -= 1
  if l > x:
    res += 1
  else:
    if r == W: res = -1
    else:
      res += max(0, r - x) + 1
      x = max(x, r)
  print(res)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
X=[list(map(int,input().split())) for i in range(H)]
P=[10**18]*H
Y=1
for i in range(H):
  if X[i][0]<=Y<=X[i][1]:
    Y=X[i][1]+1
  if Y>W:
    P[i]=-1
Y=1
for i in range(H):
  if X[i][0]<=Y<=X[i][1]:
    Y=X[i][1]+1
  if P[i]!=-1:
    P[i]=i+Y
  else:
    break
print(*P,sep='\n')

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a,l=0,0
for i in range(h):
  if a==-1:
    print(-1)
    continue
  l+=1
  q1,q2=map(lambda x:int(x)-1,input().split())
  if q1<=a and a<=q2:
    if q2==w-1:
      a=-1
      print(-1)
      continue
    l+=q2+1-a
    a=q2+1
  print(l)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())

leftRestrict = 0

out = []
for i in range(h):
    a, b = map(int, input().split())

    if a <= leftRestrict + 1:
        leftRestrict = max(b, leftRestrict)
    
    if leftRestrict < w:
        out.append(1 + i + leftRestrict)
    else:
        out.append(-1)
print('\n'.join(map(str,out)))

Submission status: Wrong Answer

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####
from collections import defaultdict as ddic, Counter, deque
import heapq, bisect, itertools
MOD = 10 ** 9 + 7

def solve(R, C, A):
    cost = 0
    x = 0
    ans = []
    for a, b in A:
        cost += 1
        if a <= x <= b:
            cost += b - x + 1
            x = b + 1
        ans.append(cost if x < C else -1)
    return ans


R, C = rrm()
A = [rrm() for _ in xrange(R)]
for i in xrange(R):
    A[i][0] -= 1
    A[i][1] -= 1

INF = int(1e15)
ans= solve(R, C, A)
for x in ans:
    if x < INF:
        print x
    else:
        print -1

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())

v = 0
ans = 0
for i in range(h):
    a,b = map(int,readline().split())
    a -= 1
    b -= 1
    if v < a:
        nv = v
    elif v <= b:
        nv = b + 1
    else:
        nv = v 

    ans += 1 + nv-v
    v = nv
    #print(v)
    if v == w:
        print(-1)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8, i8[:]), cache=True)
def main(H, W, AB):
    # 生きている左端
    x = 1
    for i in range(0, len(AB), 2):
        a, b = AB[i], AB[i + 1]
        if a <= x <= b:
            x = b + 1
        ans = i // 2 + x
        if x > W:
            ans = -1
        print(ans)

H, W = map(int, readline().split())
AB = np.array(read().split(), np.int64)

main(H, W, AB)

Submission status: Wrong Answer

Solution code:
-1

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree:

    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = [self.me]*self.n + monoid_data
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe] * (self.n * 2)


    def replace(self, index, value):
        index += self.n

        # propagation
        for shift in range(index.bit_length()-1, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # update
        self.data[index] = value
        self.lazy[index] = self.oe

        # recalculation
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def effect(self, l, r, operator):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # effect
        while l < r:
            if l % 2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r % 2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        # recalculation
        i = l0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
        i = r0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
            
        
    def folded(self, l, r):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # fold
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l % 2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)

import sys
input = sys.stdin.readline
INF = 10**7
h, w = map(int, input().split())
def fmo(m1, o1):
    if o1 == -1:
        return m1
    return o1
def foo(o1, o2):
    if o2 == -1:
        return o1
    return o2
lst_max = LazySegmentTree(list(range(w+1)), -INF, -1, max, fmo, foo)
lst_min = LazySegmentTree([0]*(w+1), INF, -1, min, fmo, foo)
for i in range(h):
    a, b = map(int, input().split())
    a -= 1
    l_max = lst_max.folded(a, b)
    lst_max.effect(a, b, -float("inf"))
    x = lst_max.folded(b, b+1)
    lst_max.replace(b, max(l_max, x))
    lst_min.effect(a, b, float("inf"))
    y = lst_min.folded(b, b+1)
    lst_min.replace(b, min(b, y))
    ans = lst_min.folded(0, w)
    if ans >= 10**6:
        print(-1)
    else:
        ans += i+1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree:

    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = [self.me]*self.n + monoid_data
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe] * (self.n * 2)


    def replace(self, index, value):
        index += self.n

        # propagation
        for shift in range(index.bit_length()-1, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # update
        self.data[index] = value
        self.lazy[index] = self.oe

        # recalculation
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def effect(self, l, r, operator):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # effect
        while l < r:
            if l % 2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r % 2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        # recalculation
        i = l0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
        i = r0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
            
        
    def folded(self, l, r):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # fold
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l % 2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
def fmo(m1, o1):
    if o1 == -1:
        return m1
    return o1
def foo(o1, o2):
    if o2 == -1:
        return o1
    return o2
lst_max = LazySegmentTree(list(range(w+1)), -float("inf"), -1, max, fmo, foo)
lst_min = LazySegmentTree([0]*(w+1), float("inf"), -1, min, fmo, foo)
for i in range(h):
    a, b = map(int, input().split())
    a -= 1
    l_max = lst_max.folded(a, b)
    lst_max.effect(a, b, -float("inf"))
    x = lst_max.folded(b, b+1)
    lst_max.replace(b, max(l_max, x))
    lst_min.effect(a, b, float("inf"))
    y = lst_min.folded(b, b+1)
    lst_min.replace(b, min(b, y))
    ans = lst_min.folded(0, w)
    if ans == float("inf"):
        print(-1)
    else:
        ans += i+1
        print(ans)