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

Solution code:
import os
import sys

import numpy as np
from heapq import heappop, heappush, heapify


def solve(inp):
    def fenwick_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def fenwick_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    def fenwick_lower_bound(arr, n, log_n, x):
        sum_ = 0
        pos = 0
        for i in range(log_n, -1, -1):
            k = pos + (1 << i)
            if k < n and sum_ + arr[k] < x:
                sum_ += arr[k]
                pos += 1 << i
        return pos + 1

    def bit_length(x):
        res = 0
        while x:
            res += 1
            x >>= 1
        return res

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    w1 = w + 1
    log_w = bit_length(w1)
    arr = np.zeros(w1 + 1, dtype=np.int64)
    for j in range(1, w1):
        arr[j] = j & -j
    fenwick_add(arr, w1, w1, 10 ** 18)
    horizontal = np.zeros(w + 1, dtype=np.int64)
    horizontal_rev = np.arange(w + 1, dtype=np.int64)
    q = [(0, j) for j in range(1, w + 1)]
    heapify(q)

    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        k = 1 if a == 1 else fenwick_sum(arr, a - 1) + 1
        c = fenwick_lower_bound(arr, w1, log_w, k)
        stack = []
        while c <= b + 1:
            stack.append(c)
            if c == w1:
                break
            k += 1
            c = fenwick_lower_bound(arr, w1, log_w, k)
        # print(a, b, k, c, horizontal, stack)

        if len(stack) == 0:
            ans[row] = row + q[0][0] + 1
            continue

        if stack[-1] == w1:
            found_nearest = True
            stack.pop()
        else:
            found_nearest = False
        stack.reverse()

        for c in stack:
            if found_nearest:
                fenwick_add(arr, w1, c, -1)
                horizontal[horizontal_rev[c]] = -1
            elif c == b + 1:
                found_nearest = True
            else:
                orig = horizontal_rev[c]
                horizontal[orig] = b + 1 - orig
                horizontal_rev[b + 1] = orig
                fenwick_add(arr, w1, c, -1)
                fenwick_add(arr, w1, b + 1, 1)
                heappush(q, (horizontal[orig], orig))
                found_nearest = True

        while q and q[0][0] != horizontal[q[0][1]]:
            heappop(q)

        if len(q) == 0:
            break

        ans[row] = row + q[0][0] + 1

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

class segtree:
    '''init_val : i-indexed (init_val[0] = self.bin[1])'''
    def __init__(self, n, init = 0, init_val=None):
        self.n = n
        self.init = init
        self.k = math.ceil(math.log2(n))
        self.add_val = 1 << self.k

        try:
            init_val[0]
        except:
            raise ValueError('init_val should be list')

        self.bins = [self.init] * (1 << (self.k + 1))
        if init_val != None:
            self.update_set(init_val)
        self.caliculate()

    def __getitem__(self, idx):  # return idx-value
        return self.bins[idx + self.add_val]

    def update_set(self, vals):
        for idx, i in enumerate(range(self.add_val, self.add_val * 2)):
            if len(vals) > idx:
                self.bins[i] = vals[idx]
            else:continue

    def compare(self, l, r):
        return min(l ,r)

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val, by=True):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        if by:
            self.bins[k] += val
        else:
            self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        #print(l, r)
        while True:
            #print(l, r)
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        #print(ret)
        return ret

class BIT:
    # init_val[0] -> bins[1]
    def __init__(self, n, init=0, init_val=None):
        '''
        n : length of vals
        init : init_val in each bins
        init_val : if specified, update is performed
        ** applioed seqs -> seq[0] -> bins[1]
        '''
        self.n = n
        self.init = init
        self.k = n.bit_length()
        self.bins = [init] * (n+1)
        self.l2 = 2 ** self.k

        if init_val !=None:
            self.update_set(init_val)

    def update_set(self, vals):
        if len(vals) > self.n:
            raise ValueError('Length is too long!')
        for i, val in enumerate(vals):
            bi = i+1
            if bi & 1:
                self.bins[bi] = val
            else:
                ret = self.init
                most_sig = (bi & -bi)
                n_bit = bi - 1
                while n_bit:
                    v = n_bit & -n_bit
                    if most_sig  >= v:break
                    ret = self.compare(ret, self.bins[n_bit])
                    n_bit -= v
                self.bins[bi] = ret

    def compare(self, l, r):
        '''comparison-criteria'''
        return l+ r

    def minus(self, val):
        '''define the negative value for caliculations'''
        return -val

    def update(self, idx, by):
        '''idx : 0-started index'''
        while idx < len(self.bins):
            self.bins[idx] = self.compare(self.bins[idx], by)
            idx += (idx & -idx)

    def get_sum(self, idx):
        '''idx: 0-indexed'''
        ans = self.init
        #idx += 1
        while idx:
            ans = self.compare(ans, self.bins[idx])
            idx -= (idx & -idx)
        return ans

    def eval_between(self, l, r):
        ''' l, r : 0-indexed '''
        return self.compare(self.get_sum(r), self.get_sum(self.get_sum(l-1)))

    def lower_bound(self, SUM):
        '''return idx sum of which is less or equal to SUM'''
        if SUM <= 0:
            return 0
        l = 0
        r = self.l2
        while r > 0:
            if l+r <= self.n and self.bins[l+r] < SUM:
                SUM -= self.bins[l + r]
                l += r
            r >>= 1
        return l + 1

    def upper_bound(self, SUM):
        '''return idx sum of which is more than SUM'''
        l = 0
        r = self.l2
        #print(r,r,r,r,r)
        while r > 0:
            if l + r <= self.n and self.bins[l + r] <= SUM:
                SUM -= self.bins[l + r]
                l += r
            r >>= 1
        return l + 1

class std_map:
    '''
    std_map function with restricted value range.
    n : max val permitted for map
    init : val if key is not specified
    '''

    def __init__(self, n, init):
        self.size = n
        self.keys = set()
        self.bit = BIT(n + 1)# memory keys
        self.dic = [init] * (n + 1)# memory vals

    def __contains__(self, key):  # keyを持つか
        return key in self.keys

    def __getitem__(self, key):  # keyに対するvalueを返す
        return self.dic[key]

    def __setitem__(self, key, value):  # dic[key]をvalueで置き換える
        if not key in self.keys:
            self.bit.update(key, 1)
            self.keys.add(key)
        self.dic[key] = value

    def remove(self, key):  # keyをmapから取り除く
        self.keys.remove(key)
        self.bit.update(key, -1)

    def lower_bound(self, k):  # k以下の最大のkeyを返す
        return self.bit.lower_bound(self.bit.get_sum(k))

    def upper_bound(self, k):  # kより大きい最小のkeyを返す
        return self.bit.upper_bound(self.bit.get_sum(k))

    def kth_key(self, k):  # k番目に小さいkeyを返す
        return self.bit.lower_bound(k)

    def kth_value(self, k):  # k番目に小さいkeyに対するvalueを返す
        return self.dic[self.kth_key(k)]

    def prev_k(self, k):  # kの一つ前のkeyを返す
        idx = self.bit.get_sum(k)
        if idx == 0:
            return -1
        return self.bit.lower_bound(idx - 1)

def run():
    H,W = map(int, sysread().split())
    tree = std_map(W, 0)
    for i in range(1, W+1):
        #print(tree.bit.bins)
        tree[i] = 0
    #print(tree.bit.bins)
    arr = [0] * (W+1)
    arr[0] = INF
    moves = segtree(W+1, init=INF, init_val=arr)

    for i in range(1, H+1):
        a, b = map(int, sysread().split())
        k = tree.upper_bound(a-1)
        min_val = INF
        while k <= b:
            min_val = min(b + 1 - k + moves[k], min_val)
            moves.update(k, INF, by=False)
            tree.remove(k)
            k = tree.upper_bound(a-1)
        if b+1 <= W and min_val < moves[b+1]:
            moves.update(b + 1, min_val, by=False)
            tree[b+1] = 1

        if moves.bins[1] == INF:
            print(-1)
        else:
            print(moves.bins[1] + i)




if __name__ == "__main__":
    run()

Submission status: Accepted

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,W = IL()
data = ILL(H)

class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def bisect(self, x):
    w = i = 0
    k = self.n
    while k:
      if i+k <= self.n and w + self.data[i+k] < x:
        w += self.data[i+k]
        i += k
      k >>= 1
    return i+1


dic = DD(int)
for i in range(W):
  dic[i+1] = i+1

members = DD(int)
for i in range(W):
  members[i+1] = 1


B = BIT(int_log(W,2)+1)

for i in range(W):
  B.add(i+1,1)
  

def calc_prev_valid(x):
  s = B.sum(x-1)
  if s == 0:
    return 0
  else:
    return B.bisect(s)
    
#print(calc_prev_valid(0))
#exit()

count_score = DD(int)
count_score[0] = W
score = 0


for i in range(H):
  

  a,b = data[i]
  now = b
  while now >= a:
    if B.el[now]:
      #print("shorisita",now)
      count_score[now-dic[now]] -= members[now]
      if not B.el[b+1]:
        dic[b+1] = dic[now]
        B.add(b+1,1)
      if b+1 < W+1:
        #print((b+1),dic[b+1])
        count_score[(b+1)-dic[b+1]] += members[now]
      B.add(now,-1)
      members[b+1] += members[now]
      members[now] = 0

    now = calc_prev_valid(now)

  #print(dic)
  #print(members)
  #print(prev_valid)
  #print(count_score)
  while True:
    if count_score[score]:
      print(score+i+1)
      break
    else:
      score += 1
    if score == W:
      for _ in range(H-i):
        print(-1)
      exit()

Submission status: Accepted

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

from collections import defaultdict

def DD(arg): return defaultdict(arg)

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

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

class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def bisect(self, x):
    w = i = 0
    k = self.n
    while k:
      if i+k <= self.n and w + self.data[i+k] < x:
        w += self.data[i+k]
        i += k
      k >>= 1
    return i+1

dic = DD(int)
for i in range(W):
  dic[i+1] = i+1

members = DD(int)
for i in range(W):
  members[i+1] = 1

B = BIT(int_log(W,2)+1)
for i in range(W):
  B.add(i+1,1)

def calc_prev_valid(x):
  s = B.sum(x-1)
  if s == 0:
    return 0
  else:
    return B.bisect(s)

count_score = DD(int)
count_score[0] = W
score = 0

for i in range(H):
  a,b = data[i]
  now = b

  while now >= a:
    if B.el[now]:
      count_score[now-dic[now]] -= members[now]
      if not B.el[b+1]:
        dic[b+1] = dic[now]
        B.add(b+1,1)
      if b+1 < W+1:
        count_score[(b+1)-dic[b+1]] += members[now]
      B.add(now,-1)
      members[b+1] += members[now]
      members[now] = 0
    now = calc_prev_valid(now)

  while True:
    if count_score[score]:
      print(score+i+1)
      break
    else:
      score += 1
    if score == W:
      for _ in range(H-i):
        print(-1)
      exit()

Submission status: Accepted

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

from collections import defaultdict

def DD(arg): return defaultdict(arg)

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

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

class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def bisect(self, x):
    w = i = 0
    k = self.n
    while k:
      if i+k <= self.n and w + self.data[i+k] < x:
        w += self.data[i+k]
        i += k
      k >>= 1
    return i+1

dic = DD(int)
for i in range(W):
  dic[i+1] = i+1

members = DD(int)
for i in range(W):
  members[i+1] = 1

B = BIT(int_log(W,2)+1)
for i in range(W):
  B.add(i+1,1)

def calc_prev_valid(x):
  s = B.sum(x-1)
  if s == 0:
    return 0
  else:
    return B.bisect(s)

count_score = DD(int)
count_score[0] = W
score = 0

for i in range(H):
  a,b = data[i]
  now = b

  while now >= a:
    if B.el[now]:
      count_score[now-dic[now]] -= members[now]
      if not B.el[b+1]:
        dic[b+1] = dic[now]
        B.add(b+1,1)
      if b+1 < W+1:
        count_score[(b+1)-dic[b+1]] += members[now]
      B.add(now,-1)
      members[b+1] += members[now]
      members[now] = 0
    now = calc_prev_valid(now)

  while True:
    if count_score[score]:
      print(score+i+1)
      break
    else:
      score += 1
    if score == W:
      for _ in range(H-i):
        print(-1)
      exit()
#  if i == 1500:
#    exit()

Submission status: Accepted

Solution code:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

# 範囲更新、最大値取得の遅延セグ木と、範囲更新、最小値取得の遅延セグ木

seg_el=1<<((W+3).bit_length()) # Segment treeの台の要素数
SEG=[1<<30]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

SEG2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def indexes(L,R):
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def updates(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
    
    while L!=R:
        if L > R:
            SEG[L]=x
            LAZY[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=x
            LAZY[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=max(SEG[ind<<1],SEG[1+(ind<<1)])

def updates2(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
    
    while L!=R:
        if L > R:
            SEG2[L]=x
            LAZY2[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG2[R]=x
            LAZY2[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG2[ind]=min(SEG2[ind<<1],SEG2[1+(ind<<1)]) 
        
def getvalues(l,r): # 区間[l,r)に関するmaxを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
            
    ANS=-1<<30

    while L!=R:
        if L > R:
            ANS=max(ANS , SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=max(ANS , SEG[R])
            R//=(R & (-R))

    return ANS

def getvalues2(l,r): # 区間[l,r)に関するminを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
            
    ANS=1<<31

    while L!=R:
        if L > R:
            ANS=min(ANS , SEG2[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=min(ANS , SEG2[R])
            R//=(R & (-R))

    return ANS

for i in range(W+1):
    updates(i,i+1,i)

for i in range(H):
    x,y = map(int,input().split())
    if x==1:
        updates(x,y+1,-(1<<30))
    else:
        MAX=getvalues(1,x)
        updates(x,y+1,MAX)

    updates2(x,y+1,1<<30)
    updates2(y+1,y+2,y+1-getvalues(y+1,y+2))

    ANS=getvalues2(1,W+1)+i+1
    if ANS>1<<28:
        sys.stdout.write(str(-1)+"\n")
    else:
        sys.stdout.write(str(ANS)+"\n")

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    inf=10**7
    class LazySegTree:
        def __init__(self, A, initialize=True, segfunc=min, ident=inf):
            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)
            self.lazy_flg = [False] * (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])
 
        def _descend(self, idx):
            lv = idx.bit_length()
            block_size = 2**self.LV
            for j in range(lv - 1, 0, -1):
                i = idx >> j
                block_size >>= 1
                x = self.lazy[i]
                if not self.lazy_flg[i]:
                    continue
                self.lazy_flg[i] = False
                self.lazy[i * 2] = x
                self.lazy[i * 2 + 1] = x + block_size
                self.lazy_flg[i * 2] = True
                self.lazy_flg[i * 2 + 1] = True
                self.data[i * 2] = x
                self.data[i * 2 + 1] = x + block_size
 
        # open interval [l, r)
        def update(self, l, r, x):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            l_ori = l
            r_ori = r
            xl = x
            xr = x + (r-l)
            block_size = 1
            while l < r:
                if l & 1:
                    self.data[l] = xl
                    self.lazy[l] = xl
                    self.lazy_flg[l] = True
                    l += 1
                    xl += block_size
                if r & 1:
                    r -= 1
                    xr -= block_size
                    self.data[r] = xr
                    self.lazy[r] = xr
                    self.lazy_flg[r] = True
                l >>= 1
                r >>= 1
                block_size <<= 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 = MI()
    ST = LazySegTree([inf] + [0] * W)
    for h in range(H):
        a, b = MI()
        ST.update(a+1, b+2, ST.query(a, a+1)+1)
        
        # L=[]
        # for i in range(W+2):
        #     L.append(ST.query(i, i+1))
        # print(L)
        
        ans = ST.query(2, W+2)
        if ans >= inf:
            print(-1)
        else:
            print(h + 1 + ans)


    mod=10**9+7

main()