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: Time Limit Exceeded

Solution code:
class lazy_segtree:
  # 区間更新をする遅延評価セグメント木
  def __init__(s, S, op, e, F, mapping, composition, id, v):
    if type(v) is int: v = [e()] * v
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.lz = [id()] * s.size
    s.e = e
    s.op = op
    s.mapping = mapping
    s.composition = composition
    s.id = id
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  # 1点更新
  def set(s, p, x):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)

  # 1点取得
  def get(s, p):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    return s.d[p]

  # 区間演算
  def prod(s, l, r):
    if l == r: return e()
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push(r >> i)
    sml, smr = s.e(), s.e()
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)

  # 全体演算
  def all_prod(s): return s.d[1]

  # 1点写像
  def apply(s, p, f):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = s.mapping(f, s.d[p])
    for i in range(1, s.log + 1): s.update(p >> i)

  # 区間写像
  def apply(s, l, r, f):
    if l == r: return
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push((r - 1) >> i)
    l2, r2 = l, r
    while l < r:
      if l & 1: 
        sml = s.all_apply(l, f)
        l += 1
      if r & 1:
        r -= 1
        smr = s.all_apply(r, f)
      l >>= 1
      r >>= 1
    l, r = l2, r2
    for i in range(1, s.log + 1):
      if (((l >> i) << i) != l): s.update(l >> i)
      if (((r >> i) << i) != r): s.update((r - 1) >> i)
   
  # L固定時の最長区間のR
  def max_right(l, g):
    if l == s._n: return _n
    l += s.size
    for i in range(s.log, 0, -1): s.push(l >> i)
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          s.push(l)
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n

  # R固定時の最長区間のL
  def min_left(r, g):
    if r == 0: return 0
    r += s.size
    for i in range(s.log, 0, -1): s.push((r - 1) >> i)
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          s.push(r)
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0

  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def all_apply(s, k, f):
    s.d[k] = s.mapping(f, s.d[k])
    if k < s.size: s.lz[k] = s.composition(f, s.lz[k])
  def push(s, k):
    s.all_apply(2 * k, s.lz[k])
    s.all_apply(2 * k + 1, s.lz[k])
    s.lz[k] = s.id()
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x
  # debug
  def printValue(s):
    L = []
    for i in range(s._n):
      L.append(s.get(i))
    print(L)
#-------最強ライブラリここまで------

def op(l, r):
  return min(l, r)

def e():
  return 10 ** 10

def mapping(f, x):
  return f + x

def composition(f, g):
  return f + g

def mapping2(f, x):
  return f

def composition2(f, g):
  return g + f

def id():
  return 0

_ = 0

H, W = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(H)]
 
seg = lazy_segtree(_, op, e, _, mapping, composition, id, [0] * W)
segL = lazy_segtree(_, op, e, _, mapping2, composition2, id,[0] *  W)
 
inf = 10 ** 10
for i in range(H):
  a, b = AB[i]
  a -= 1
  b -= 1
  if a == 0:
    s = inf
  else:
    s = min(inf, seg.get(a - 1) + 1)
  while a <= b:
    toa = segL.get(a)
    if toa == 0:
      seg.set(a, min(inf, seg.get(a) + s))
      segL.set(a, b + 1)
      s = min(inf, s + 1)
      a += 1
    else:
      t = s - seg.get(a)
      seg.apply(a, min(b + 1, toa), min(inf, t))
      segL.apply(a, min(b + 1, toa), b + 1)
      a = toa
      if a > b: break
      s = seg.get(a - 1) + 1
 
  ans = seg.all_prod() + i + 1
  if ans >= inf:
    print(-1)
  else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
B = []
for _ in range(H):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

path = dict((i, i)for i in range(1, W+1))
diff = dict((i, 0)for i in range(1, W+1))
for k in range(H):
    updates = []
    max_s = None
    for s, t in path.items():
        if A[k] <= t <= B[k]:
            updates.append(s)
        if t == B[k] + 1:
            max_s = s

    if updates:
        if not max_s:
            max_s = max(updates)
        if B[k] == W:
            del path[max_s]
            del diff[max_s]
        else:
            path[max_s] = B[k] + 1
            diff[max_s] = B[k] + 1 - max_s
        for x in updates:
            if x == max_s:
                continue
            del path[x]
            del diff[x]

    if not path:
        print("-1\n"*(H-k), end="")
        exit()

    min_length = min(diff.values())
    print(min_length + k + 1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
B = []
for _ in range(H):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

path = dict((i, i)for i in range(1, W+1))
diff = dict((i, 0)for i in range(1, W+1))
for k in range(H):
    updates = []
    for s, t in path.items():
        if A[k] <= t <= B[k]:
            updates.append(s)

    if updates:
        max_s = max(updates)
        if B[k] == W:
            del path[max_s]
            del diff[max_s]
        else:
            path[max_s] = B[k] + 1
            diff[max_s] = B[k] + 1 - max_s
        for x in updates:
            if x == max_s:
                continue
            del path[x]
            del diff[x]

    if not path:
        print("-1\n"*(H-k), end="")
        exit()

    min_length = min(diff.values())
    print(min_length + k + 1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
B = []
for _ in range(H):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

path = dict((i, i)for i in range(1, W+1))
diff = dict((i, 0)for i in range(1, W+1))
for k in range(H):
    updates = []
    for s, t in path.items():
        if A[k] <= t <= B[k]:
            updates.append(s)
            
    if updates:
        max_s = max(updates)
        updates.remove(max_s)
        if B[k] == W:
            del path[max_s]
            del diff[max_s]
        else:
            path[max_s] = B[k] + 1
            diff[max_s] = B[k] + 1 - max_s
        for x in updates:
            del path[x]
            del diff[x]

    if not path:
        print("-1\n"*(H-k), end="")
        exit()

    min_length = min(diff.values())
    print(min_length + k + 1)

Submission status: Time Limit Exceeded

Solution code:
R, C = map(int, input().split(" "))
g = [[0 for i in range(C)] for j in range(R+1)]
ref = [[0 for i in range(C)] for j in range(R+1)]
INF = 2000000
for i in range(R):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    for j in range(a, b + 1):
        ref[i][j] = 1
for r in range(R+1):
    for c in range(C):
        if r == 0 and c == 0:
            g[r][c] = INF if ref[r][c] == 1 else 0
        elif r == 0:
            g[r][c] = g[r][c - 1] + 1
        elif c == 0:
            g[r][c] = INF if ref[r - 1][c] == 1 else g[r - 1][c] + 1
        else:
            g[r][c] = min((INF if ref[r - 1][c] == 1 else g[r - 1][c] + 1),
                          g[r][c - 1] + 1)
#print(g)
for i in range(1,R+1):
    print(-1 if min(g[i]) >= INF else min(g[i]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import random
from numba import jit
rnd = False

INF = 10**6
if rnd:
    H, W = 10**5, 10**5
else:
    H, W = list(map(int, input().split()))

A, B = np.zeros(H+2, dtype=np.int64), np.zeros(H+2, dtype=np.int64)
for i in range(1, H+1):
    if rnd:
        A[i] = random.choice(range(1, W))
        B[i] = random.choice(range(A[i], W))
    else:
        A[i], B[i] = list(map(int, input().split()))

pos = np.array(range(1, W+1))
init = np.array(range(1, W+1))

@jit(nopython=True)
def nxt(pos, init, a, b):
    if (len(pos)==0): return(pos, init, 0)
    lft = np.searchsorted(pos, a, side='left')
    rgt = np.searchsorted(pos, b, side='right')
    if b == W:
        pos = pos[:lft]
        init = init[:lft]
    elif lft == rgt: # nothing affected
        pass
    else:
        pos[lft:rgt] = b+1
        pos = np.concatenate((pos[:lft], pos[rgt-1:]))
        init = np.concatenate((init[:lft], init[rgt-1:]))
    if (len(pos)==0):
        return(pos, init, 0)
    else:
        return((pos, init, np.min(pos-init)))

for h in range(1, H+1):
    (pos, init, s) = nxt(pos, init, A[h], B[h])
    if (len(pos)==0):
        print (-1)
        pass
    else:
        print(s+h)
        pass

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import random
rnd = False

INF = 10**6
if rnd:
    H, W = 10**5, 10**5
else:
    H, W = list(map(int, input().split()))

A, B = np.zeros(H+2, dtype=np.int64), np.zeros(H+2, dtype=np.int64)
for i in range(1, H+1):
    if rnd:
        A[i] = random.choice(range(1, W))
        B[i] = random.choice(range(A[i], W))
    else:
        A[i], B[i] = list(map(int, input().split()))

pos = np.array(range(1, W+1))
init = np.array(range(1, W+1))

def nxt(pos, init, a, b):
    if (len(pos)==0): return(pos, init, 0)
    lft = np.searchsorted(pos, a, side='left')
    rgt = np.searchsorted(pos, b, side='right')
    if b == W:
        pos = pos[:lft]
        init = init[:lft]
    elif lft == rgt: # nothing affected
        pass
    else:
        pos = np.concatenate((pos[:lft], [b+1], pos[rgt:]))
        init = np.concatenate((init[:lft], init[rgt-1:]))
    if (len(pos)==0):
        return(pos, init, 0)
    else:
        return((pos, init, np.min(pos-init)))

for h in range(1, H+1):
    (pos, init, s) = nxt(pos, init, A[h], B[h])
    if (len(pos)==0):
        print (-1)
        pass
    else:
        print(s+h)
        pass

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
INF = 10**6
H, W = list(map(int, input().split()))
A, B = np.zeros(H+2), np.zeros(H+2)
for i in range(1, H+1):
    A[i], B[i] = list(map(int, input().split()))

pos = np.array(range(1, W+1))
init = np.array(range(1, W+1))

@jit(nopython=True)
def nxt(pos, a, b):
    lft = np.searchsorted(pos, a, side='left')
    rgt = np.searchsorted(pos, b, side='right')
    if b == W:
        n = INF
    else:
        n = b+1
    pos[lft:rgt] = n
    return(np.min(pos-init))

for h in range(1, H+1):
    s = nxt(pos, A[h], B[h])
    if (pos[0]==INF):
        print (-1)
    else:
        print(s+h)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
INF = 10**6
H, W = list(map(int, input().split()))
A, B = np.zeros(H+2), np.zeros(H+2)
for i in range(1, H+1):
    A[i], B[i] = list(map(int, input().split()))

pos = np.array(range(1, W+1))
init = np.array(range(1, W+1))

@jit(nopython=True)
def nxt(pos, a, b):
    lft = np.searchsorted(pos, a, side='left')
    rgt = np.searchsorted(pos, b, side='right')
    if b == W:
        n = INF
    else:
        n = b+1
    pos[lft:rgt] = n

for h in range(1, H+1):
    nxt(pos, A[h], B[h])
    if (pos[0]==INF):
        print (-1)
    else:
        print(min(pos-init)+h)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
INF = 10**6
H, W = list(map(int, input().split()))
A, B = [0]*(H+2), [0]*(H+2)
for i in range(1, H+1):
    A[i], B[i] = list(map(int, input().split()))

pos = np.array(range(1, W+1))
init = np.array(range(1, W+1))

@jit
def nxt(pos):
    lft = np.searchsorted(pos, A[h], side='left')
    rgt = np.searchsorted(pos, B[h], side='right')
    if B[h] == W:
        n = INF
    else:
        n = B[h]+1
    pos[lft:rgt] = n

for h in range(1, H+1):
    nxt(pos)
    if (pos[0]==INF):
        print (-1)
    else:
        print(min(pos-init)+h)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit, stdin
from random import random

readline = stdin.readline
setrecursionlimit(10 ** 6)


class TreapNode:
    def __init__(self, key, value=None):
        self._key = key
        self._value = value
        self._priority = random()
        self._left = None
        self._right = None

    @property
    def key(self):
        return self._key

    @property
    def value(self):
        return self._value


def treap_rotate_right(n):
    l = n._left
    n._left = l._right
    l._right = n
    return l


def treap_rotate_left(n):
    r = n._right
    n._right = r._left
    r._left = n
    return r


def treap_find(n, key):
    if n is None:
        return None
    if n.key == key:
        return n
    if key < n.key:
        return treap_find(n._left, key)
    else:
        return treap_find(n._right, key)


def treap_lower_bound(n, key):
    if n is None:
        return None
    if n.key < key:
        return treap_lower_bound(n._right, key)
    t = treap_lower_bound(n._left, key)
    if t is None:
        return n
    else:
        return t


def treap_insert(n, key, value=None):
    if n is None:
        return TreapNode(key, value)
    if n.key == key:
        raise Exception('duplicated key')
    if n.key > key:
        n._left = treap_insert(n._left, key, value)
        if n._priority > n._left._priority:
            n = treap_rotate_right(n)
    else:
        n._right = treap_insert(n._right, key, value)
        if n._priority > n._right._priority:
            n = treap_rotate_left(n)
    return n


def treap_delete(n, key):
    if n is None:
        raise Exception('non-existent key')
    if n.key > key:
        n._left = treap_delete(n._left, key)
        return n
    if n.key < key:
        n._right = treap_delete(n._right, key)
        return n

    # n._key == key
    if n._left is None and n._right is None:
        return None

    if n._left is None:
        n = treap_rotate_left(n)
    elif n._right is None:
        n = treap_rotate_right(n)
    else:
        # n._left is not None and n._right is not None
        if n._left._priority < n._right._priority:
            n = treap_rotate_right(n)
        else:
            n = treap_rotate_left(n)
    return treap_delete(n, key)


def treap_size(n):
    if n is None:
        return 0
    return 1 + treap_size(n._left) + treap_size(n._right)


def treap_str(n):
    if n is None:
        return ""
    result = []
    if n._left is not None:
        result.append(treap_str(n._left))
    if n.value is None:
        result.append("%d" % (n.key))
    else:
        result.append("%d:%d" % (n.key, n.value))
    if n._right is not None:
        result.append(treap_str(n._right))
    return ' '.join(result)


def treap_min(n):
    if n is None:
        raise Exception('no nodes')
    if n._left is None:
        return n.key
    else:
        return treap_min(n._left)


def treap_max(n):
    if n is None:
        raise Exception('no nodes')
    if n._right is None:
        return n.key
    else:
        return treap_max(n._right)


class Treap:
    def __init__(self):
        self._root = None
        self._size = 0
        self._min = None
        self._max = None

    def find(self, key):
        return treap_find(self._root, key)

    def lower_bound(self, key):
        return treap_lower_bound(self._root, key)

    def insert(self, key, value=None):
        self._root = treap_insert(self._root, key, value)
        self._size += 1
        if self._size == 1:
            self._min = key
            self._max = key
        else:
            if self._min is not None:
                self._min = min(self._min, key)
            if self._max is not None:
                self._max = max(self._max, key)

    def delete(self, key):
        self._root = treap_delete(self._root, key)
        self._size -= 1
        if self._size == 0:
            self._min = None
            self._max = None
        else:
            if self._min == key:
                self._min = None
            if self._max == key:
                self._max = None

    def __len__(self):
        return self._size

    def __str__(self):
        return treap_str(self._root)

    def min(self):
        if self._min is None:
            self._min = treap_min(self._root)
        return self._min

    def max(self):
        if self._max is None:
            self._max = treap_max(self._root)
        return self._max


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

candidates = Treap()
moves = Treap()

for i in range(W):
    candidates.insert(i, i)
moves.insert(0, W)

result = []
for i in range(H):
    A, B = map(int, readline().split())
    A -= 1

    r = -1
    while True:
        n = candidates.lower_bound(A)
        if n is None or n.key > B:
            break
        r = max(r, n.value)
        t = moves.find(n.key - n.value)
        moves.delete(t.key)
        if t.value != 1:
            moves.insert(t.key, t.value - 1)
        candidates.delete(n.key)

    if r != -1 and B != W:
        t = B - r
        n = moves.find(t)
        if n is None:
            moves.insert(t, 1)
        else:
            moves.delete(n.key)
            moves.insert(n.key, n.value + 1)
        candidates.insert(B, r)

    if len(moves) == 0:
        result.append(-1)
    else:
        result.append(moves.min() + i + 1)

print(*result, sep='\n')

Submission status: Time Limit Exceeded

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

class SegTreeFlag():
    def segFunc(self, x, y):
        return x+y
    def searchIndexFunc(self, val):
        return val > 0
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segFunc(self.seg[2*i+1],self.seg[2*i+2])
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res
    def getLargestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R)//2
            if self.searchIndexFunc(self.query(P, R)):
                L = P
            else:
                R = P
        return L
    def getSmallestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R+1)//2
            if self.searchIndexFunc(self.query(L, P)):
                R = P
            else:
                L = P
        return L

class SegTreeMin():
    def segFunc(self, x, y):
        if x < y:
            return x
        else:
            return y
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segFunc(self.seg[2*i+1],self.seg[2*i+2])
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res

h, w = map(int, input().split())
wall = [list(map(int, input().split())) for _ in range(h)]
ans = [-1 for _ in range(h)]
segflag = SegTreeFlag(0, [1 for _ in range(w+2)])
segmin = SegTreeMin(float("inf"), [0 for _ in range(w+2)])
segmin.update(0, float("inf"))
for i in range(h):
    idx = segflag.getLargestIndex(0, wall[i][1]+2)
    if idx < wall[i][1]+1:
        segflag.update(wall[i][1]+1, 1)
        segmin.update(wall[i][1]+1, segmin.query(idx, idx+1)+(wall[i][1]+1-idx))
    cnt = segflag.query(wall[i][0], wall[i][1]+1)
    for _ in range(cnt):
        idx = segflag.getSmallestIndex(wall[i][0], wall[i][1]+1)
        segflag.update(idx, 0)
        segmin.update(idx, float("inf"))
    tmp = segmin.query(0, w+1)
    if tmp != float("inf"):
        ans[i] = tmp + i + 1
    else:
        break
for v in ans:
    print(v)

Submission status: Time Limit Exceeded

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

class SegTreeFlag():
    def segFunc(self, x, y):
        return x+y
    def searchIndexFunc(self, val):
        return val > 0
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segFunc(self.seg[2*i+1],self.seg[2*i+2])
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res
    def getLargestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R)//2
            if self.searchIndexFunc(self.query(P, R)):
                L = P
            else:
                R = P
        return L
    def getSmallestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R+1)//2
            if self.searchIndexFunc(self.query(L, P)):
                R = P
            else:
                L = P
        return L

class SegTreeMin():
    def segFunc(self, x, y):
        if x < y:
            return x
        else:
            return y
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segFunc(self.seg[2*i+1],self.seg[2*i+2])
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res

h, w = map(int, input().split())
wall = [list(map(int, input().split())) for _ in range(h)]
ans = [-1]*h
segflag = SegTreeFlag(0, [1]*(w+2))
segmin = SegTreeMin(float("inf"), [0]*(w+2))
segmin.update(0, float("inf"))
for i in range(h):
    idx = segflag.getLargestIndex(0, wall[i][1]+2)
    if idx < wall[i][1]+1:
        segflag.update(wall[i][1]+1, 1)
        segmin.update(wall[i][1]+1, segmin.query(idx, idx+1)+(wall[i][1]+1-idx))
    cnt = segflag.query(wall[i][0], wall[i][1]+1)
    for _ in range(cnt):
        idx = segflag.getSmallestIndex(wall[i][0], wall[i][1]+1)
        segflag.update(idx, 0)
        segmin.update(idx, float("inf"))
    tmp = segmin.query(0, w+1)
    if tmp != float("inf"):
        ans[i] = tmp + i + 1
    else:
        break
for v in ans:
    print(v)