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

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

# 区間更新、区間最小
class LazySegMin:
    def __init__(self, aa):
        inf = 10 ** 16
        n = 1 << (len(aa) - 1).bit_length()
        tree = [inf] * (2 * n)
        lazy = [None] * (2 * n)
        tree[n:n + len(aa)] = aa
        for u in range(n - 1, -1, -1):
            tree[u] = min(tree[u * 2], tree[u * 2 + 1])
        self.tree = tree
        self.lazy = lazy
        self.n = n
        self.inf = inf

    def update(self, l, r, a, u=1, tl=0, tr=-1):
        if tr == -1: tr = self.n
        self._eval(u, tl, tr)
        if r <= tl or tr <= l: return
        if l <= tl and tr <= r:
            self.lazy[u] = a
            self._eval(u, tl, tr)
            return
        tm = (tl + tr) // 2
        self.update(l, r, a, u * 2, tl, tm)
        self.update(l, r, a, u * 2 + 1, tm, tr)
        self.tree[u] = min(self.tree[u * 2], self.tree[u * 2 + 1])

    def min(self, l, r, u=1, tl=0, tr=-1):
        if tr == -1: tr = self.n
        if r <= tl or tr <= l: return self.inf
        self._eval(u, tl, tr)
        if l <= tl and tr <= r: return self.tree[u]
        tm = (tl + tr) // 2
        return min(self.min(l, r, u * 2, tl, tm), self.min(l, r, u * 2 + 1, tm, tr))

    def _eval(self, u, l, r):
        if self.lazy[u] == None: return
        self.tree[u] = self.lazy[u]
        if l + 1 < r:
            self.lazy[u * 2] = self.lazy[u]
            self.lazy[u * 2 + 1] = self.lazy[u]
        self.lazy[u] = None

from heapq import *

inf=10**9
h,w=MI()

cost=[0]*w
invaid=0
hp=[(0,i) for i in range(w)]
heapify(hp)
st=LazySegMin(list(range(0,-w,-1)))
to0=lambda a,k:(a>>(k+1))<<(k+1)|(a&((1<<k)-1))


for i in range(h):
    l,r=MI()
    l-=1
    if r<w:
        mn=st.min(l,r+1)
        st.update(r,r+1,mn)
        invaid=to0(invaid,r)
        cost[r]=mn+r
        heappush(hp,(mn+r,r))
    st.update(l,r,inf)
    invaid|=((1<<r-l)-1)<<l
    while hp:
        c,j=hp[0]
        if invaid>>j&1 or cost[j]!=c:heappop(hp)
        else:
            print(c+i+1)
            break
    else:print(-1)
    # print(l,r,cost,bin(invaid),hp)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

# 区間更新、区間最小
class LazySegMin:
    def __init__(self, aa):
        inf = 10 ** 16
        n = 1 << (len(aa) - 1).bit_length()
        tree = [inf] * (2 * n)
        lazy = [None] * (2 * n)
        tree[n:n + len(aa)] = aa
        for u in range(n - 1, -1, -1):
            tree[u] = min(tree[u * 2], tree[u * 2 + 1])
        self.tree = tree
        self.lazy = lazy
        self.n = n
        self.inf = inf

    def update(self, l, r, a, u=1, tl=0, tr=-1):
        if tr == -1: tr = self.n
        self._eval(u, tl, tr)
        if r <= tl or tr <= l: return
        if l <= tl and tr <= r:
            self.lazy[u] = a
            self._eval(u, tl, tr)
            return
        tm = (tl + tr) // 2
        self.update(l, r, a, u * 2, tl, tm)
        self.update(l, r, a, u * 2 + 1, tm, tr)
        self.tree[u] = min(self.tree[u * 2], self.tree[u * 2 + 1])

    def min(self, l, r, u=1, tl=0, tr=-1):
        if tr == -1: tr = self.n
        if r <= tl or tr <= l: return self.inf
        self._eval(u, tl, tr)
        if l <= tl and tr <= r: return self.tree[u]
        tm = (tl + tr) // 2
        return min(self.min(l, r, u * 2, tl, tm), self.min(l, r, u * 2 + 1, tm, tr))

    def _eval(self, u, l, r):
        if self.lazy[u] == None: return
        self.tree[u] = self.lazy[u]
        if l + 1 < r:
            self.lazy[u * 2] = self.lazy[u]
            self.lazy[u * 2 + 1] = self.lazy[u]
        self.lazy[u] = None

from heapq import *

inf=10**9
h,w=MI()

cost=[0]*w
invaid=0
hp=[(0,i) for i in range(w)]
heapify(hp)
st=LazySegMin(list(range(0,-w,-1)))
to0=lambda a,k:(a>>(k+1))<<(k+1)|((1<<k)-1)


for i in range(h):
    l,r=MI()
    l-=1
    if r<w:
        mn=st.min(l,r+1)
        st.update(r,r+1,mn)
        invaid=to0(invaid,r)
        cost[r]=mn+r
        heappush(hp,(mn+r,r))
    st.update(l,r,inf)
    invaid|=((1<<r-l)-1)<<l
    while hp:
        c,j=hp[0]
        if invaid>>j&1 or cost[j]!=c:heappop(hp)
        else:
            print(c+i+1)
            break
    else:print(-1)
    # print(l,r,cost,bin(invaid),hp)

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    H, W = list(map(int, input().split(" ")))
    AB_arr2 =[]
    for i in range(H):
        AB_arr2.append(list(map(int, input().split(" "))))
        AB_arr2[i][0] -=1
        AB_arr2[i][1] -=1
    state_d = {}
    cnt_d = {}
    roop_d = []

    for i in range(W):
        state_d[i] = i
        cnt_d[i] = 0
        roop_d.append(i)
    roop2_d = copy.copy(roop_d)

    for i in range (H):
        for j in roop_d:
            cnt_d[j] += 1
            if AB_arr2[i][0] <= state_d[j] and AB_arr2[i][1] >= state_d[j]:
                if state_d[j] == W-1 or (j + 1) in state_d:
                    del state_d[j], cnt_d[j]
                    roop2_d.remove(j)
                else:
                    cnt_d[j] += AB_arr2[i][1] - state_d[j] + 1
                    state_d[j] = AB_arr2[i][1] + 1
        roop_d = copy.copy(roop2_d)
        if cnt_d:
            print(min(cnt_d.values()))
        else:
            print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

# 区間更新、区間最大
class LazySegMax:
    def __init__(self, aa):
        inf = 10 ** 16
        n = 1 << (len(aa) - 1).bit_length()
        tree = [-inf] * (2 * n)
        lazy = [None] * (2 * n)
        tree[n:n + len(aa)] = aa
        for u in range(n - 1, 0, -1): tree[u] = max(tree[u * 2], tree[u * 2 + 1])
        self.tree = tree
        self.lazy = lazy
        self.n = n
        self.inf = inf

    def update(self, l, r, a, u=1, tl=0, tr=-1):
        if tr == -1: tr = self.n
        self._eval(u)
        if r <= tl or tr <= l: return
        if l <= tl and tr <= r:
            self.lazy[u] = a
            self._eval(u)
            return
        tm = (tl + tr) // 2
        self.update(l, r, a, u * 2, tl, tm)
        self.update(l, r, a, u * 2 + 1, tm, tr)
        self.tree[u] = max(self.tree[u * 2], self.tree[u * 2 + 1])

    def max(self, l, r, u=1, tl=0, tr=-1):
        if tr == -1: tr = self.n
        if r <= tl or tr <= l: return -self.inf
        self._eval(u)
        if l <= tl and tr <= r: return self.tree[u]
        tm = (tl + tr) // 2
        return max(self.max(l, r, u * 2, tl, tm), self.max(l, r, u * 2 + 1, tm, tr))

    def _eval(self, u):
        if self.lazy[u]==None:return
        self.tree[u] = self.lazy[u]
        if u < self.n:
            self.lazy[u * 2] = self.lazy[u]
            self.lazy[u * 2 + 1] = self.lazy[u]
        self.lazy[u]=None

# 区間更新、区間最小
class LazySegMin:
    def __init__(self, aa):
        inf = 10 ** 16
        n = 1 << (len(aa) - 1).bit_length()
        tree = [inf] * (2 * n)
        lazy = [None] * (2 * n)
        tree[n:n + len(aa)] = aa
        for u in range(n - 1, -1, -1):
            tree[u] = min(tree[u * 2], tree[u * 2 + 1])
        self.tree = tree
        self.lazy = lazy
        self.n = n
        self.inf = inf

    def update(self, l, r, a, u=1, tl=0, tr=-1):
        if tr == -1: tr = self.n
        self._eval(u, tl, tr)
        if r <= tl or tr <= l: return
        if l <= tl and tr <= r:
            self.lazy[u] = a
            self._eval(u, tl, tr)
            return
        tm = (tl + tr) // 2
        self.update(l, r, a, u * 2, tl, tm)
        self.update(l, r, a, u * 2 + 1, tm, tr)
        self.tree[u] = min(self.tree[u * 2], self.tree[u * 2 + 1])

    def min(self, l, r, u=1, tl=0, tr=-1):
        if tr == -1: tr = self.n
        if r <= tl or tr <= l: return self.inf
        self._eval(u, tl, tr)
        if l <= tl and tr <= r: return self.tree[u]
        tm = (tl + tr) // 2
        return min(self.min(l, r, u * 2, tl, tm), self.min(l, r, u * 2 + 1, tm, tr))

    def _eval(self, u, l, r):
        if self.lazy[u] == None: return
        self.tree[u] = self.lazy[u]
        if l + 1 < r:
            self.lazy[u * 2] = self.lazy[u]
            self.lazy[u * 2 + 1] = self.lazy[u]
        self.lazy[u] = None

inf=10**9
h,w=MI()
# first position
fp=LazySegMax(list(range(w)))
# cost
cs=LazySegMin([0]*w)

for i in range(h):
    l,r=MI()
    l-=1
    if r<w:
        mxp=fp.max(l,r+1)
        fp.update(r,r+1,mxp)
        cs.update(r,r+1,r-mxp)
    fp.update(l, r, -1)
    cs.update(l,r,inf)
    cur=cs.min(0,w)
    if cur==inf:print(-1)
    else:print(cur+i+1)

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    H, W = list(map(int, input().split(" ")))
    AB_arr2 =[]
    for i in range(H):
        AB_arr2.append(list(map(int, input().split(" "))))
        AB_arr2[i][0] -=1
        AB_arr2[i][1] -=1
    state_d = {}
    cnt_d = {}
    roop_d = [i for i in range(W)]

    for i in range(W):
        state_d[i] = i
        cnt_d[i] = 0
    roop2_d = copy.copy(roop_d)

    for i in range (H):
        for j in roop_d:
            if j in state_d:
                if AB_arr2[i][0] <= state_d[j] and AB_arr2[i][1] >= state_d[j]:
                    if state_d[j] == W-1 or (j + 1) in state_d:
                        del state_d[j], cnt_d[j]
                        roop2_d.remove(j)
                    else:
                        cnt_d[j] += AB_arr2[i][1] - state_d[j] + 1
                        state_d[j] = AB_arr2[i][1] + 1
            if j in cnt_d:
                cnt_d[j] += 1
        roop_d = copy.copy(roop2_d)
        if cnt_d:
            print(min(cnt_d.values()))
        else:
            print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class segTreeRUQ:
  # 区間更新をする遅延評価セグメント木
  inf = 10**10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [0] * (2 * s.N)
    s.L = [None] * (2 * s.N)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i + 1, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, x):
    s.propagates(*s.getIndex(x, x + 1))
    return s.T[x + s.N - 1]
  def getArea(s, l, r):
    s.propagates(*s.getIndex(l, r))
    L = l + s.N
    R = r + s.N
    p = s.inf
    while L < R:
      if R & 1:
        R -= 1
        p = s.do(p, s.T[R - 1])
      if L & 1:
        p = s.do(p, s.T[L - 1])
        L += 1
      L >>= 1
      R >>= 1
    return p
  def getIndex(s, l, r):
    L = l + s.N
    R = r + s.N
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
      if R <= rm:
        yield R
      if L <= lm:
        yield L
      L >>= 1
      R >>= 1
    while L:
      yield L
      L >>= 1
  def propagates(s, *ids):
    for i in reversed(ids):
      v = s.L[i - 1]
      if v is None: continue
      s.L[2 * i - 1] = s.T[2 * i - 1] = s.L[2 * i] = s.T[2 * i] = v
      s.L[i - 1] = None
  # 区間更新
  def updateArea(s, l, r, x):
    *ids, = s.getIndex(l, r)
    s.propagates(*ids)
    L = s.N + l
    R = s.N + r
    while L < R:
      if R & 1:
        R -= 1
        s.L[R - 1] = s.T[R - 1] = x
      if L & 1:
        s.L[L - 1] = s.T[L - 1] = x
        L += 1
      L >>= 1
      R >>= 1
    for i in ids:
      s.T[i - 1] = s.do(s.T[2 * i - 1], s.T[2 * i])
  # debug
  def printValue(s):
    L = []
    for i in range(s.N):
      L.append(s.get(i))
    print(L)

class segTreeRAQ:
  # 区間加算をする遅延評価セグメント木
  inf = 10**10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [0] * (2 * s.N)
    s.L = [0] * (2 * s.N)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i + 1, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, x):
    s.propagates(*s.getIndex(x, x + 1))
    return s.T[x + s.N - 1]
  def getArea(s, l, r):
    s.propagates(*s.getIndex(l, r))
    L = l + s.N
    R = r + s.N
    p = s.inf
    while L < R:
      if R & 1:
        R -= 1
        p = s.do(p, s.T[R - 1])
      if L & 1:
        p = s.do(p, s.T[L - 1])
        L += 1
      L >>= 1
      R >>= 1
    return p
  def getIndex(s, l, r):
    L = l + s.N
    R = r + s.N
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
      if R <= rm:
        yield R
      if L <= lm:
        yield L
      L >>= 1
      R >>= 1
    while L:
      yield L
      L >>= 1
  def propagates(s, *ids):
    for i in reversed(ids):
      v = s.L[i - 1]
      if not v: continue
      s.L[2 * i - 1] += v
      s.L[2 * i] += v
      s.T[2 * i - 1] += v
      s.T[2 * i] += v
      s.L[i - 1] = 0
  # 区間加算
  def addArea(s, l, r, x):
    L = s.N + l
    R = s.N + r
    while L < R:
      if R & 1:
        R -= 1
        s.L[R - 1] = min(inf, s.L[R - 1] + x)
        s.T[R - 1] = min(inf, s.T[R - 1] + x)
      if L & 1:
        s.L[L - 1] = min(inf, s.L[L - 1] + x)
        s.T[L - 1] = min(inf, s.T[L - 1] + x)
        L += 1
      L >>= 1
      R >>= 1
    for i in s.getIndex(l, r):
      s.T[i - 1] = s.do(s.T[2 * i - 1], s.T[2 * i]) + s.L[i - 1]
  # debug
  def printValue(s):
    L = []
    for i in range(s.N):
      L.append(s.get(i))
    print(L)

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

seg = segTreeRAQ(W)
segL = segTreeRUQ(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.update(a, min(inf, seg.get(a) + s))
      segL.update(a, b + 1)
      s = min(inf, s + 1)
      a += 1
    else:
      t = s - seg.get(a)
      seg.addArea(a, min(b + 1, toa), min(inf, t))
      segL.updateArea(a, min(b + 1, toa), b + 1)
      a = toa
      if a > b: break
      s = seg.get(a - 1) + 1

  ans = seg.getArea(0, W) + i + 1
  if ans >= inf:
    print(-1)
  else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys 
input = sys.stdin.readline
from heapq import heappop,heappush

class BIT:
    def __init__(self, n):
        self.tree = [1]*(n+1)
        self.size = len(self.tree)
        self.tree[0] = 0
 
    def build(self):
        for i in range(self.size):
            j = i + (i & (-i))
            if j < self.size:
                self.tree[j] += self.tree[i]
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i += i & -i

    # 総和がx以上になる位置のindex をbinary search
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri < self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

h,w = map(int,input().split())
bit = BIT(w+3)
bit.build()

q = [0]*(w)
dp = [0]*(w+3)
dp[0] = -1
rm_q = []

for i in range(h):
    a,b = map(int,input().split())
    for x in [a-1,b+1]:
        if x == 0 or x == w+1:
            continue
        if dp[x] != -1:
            continue
        k = bit.sum(x)
        if k >= 1:
            xl = bit.bsearch(k)
            dp[x] = dp[xl]+(x-xl)
            bit.add(x,1)
            heappush(q,dp[x])
    k = bit.sum(a-1)+1
    while True:
        x = bit.bsearch(k)
        if x > b:
            break
        bit.add(x,-1)
        heappush(rm_q, dp[x])
        dp[x] = -1
    while rm_q and rm_q[0] == q[0]:
        heappop(rm_q)
        heappop(q)
    if q == []:
        print(-1)
    else:
        print(q[0]+i+1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush

class BIT:
    def __init__(self, n):
        self.tree = [1]*(n+1)
        self.size = len(self.tree)
        self.tree[0] = 0
 
    def build(self):
        for i in range(self.size):
            j = i + (i & (-i))
            if j < self.size:
                self.tree[j] += self.tree[i]
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i += i & -i

    # 総和がx以上になる位置のindex をbinary search
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri < self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

h,w = map(int,input().split())
bit = BIT(w+3)
bit.build()

q = [0]*(w)
dp = [0]*(w+3)
dp[0] = -1
rm_q = []

for i in range(h):
    a,b = map(int,input().split())
    for x in [a-1,b+1]:
        if x == 0 or x == w+1:
            continue
        if dp[x] != -1:
            continue
        k = bit.sum(x)
        if k >= 1:
            xl = bit.bsearch(k)
            dp[x] = dp[xl]+(x-xl)
            bit.add(x,1)
            heappush(q,dp[x])
    k = bit.sum(a-1)+1
    while True:
        x = bit.bsearch(k)
        if x > b:
            break
        bit.add(x,-1)
        heappush(rm_q, dp[x])
        dp[x] = -1
    while rm_q and rm_q[0] == q[0]:
        heappop(rm_q)
        heappop(q)
    if q == []:
        print(-1)
    else:
        print(q[0]+i+1)

Submission status: Time Limit Exceeded

Solution code:

def main():
    H, W = list(map(int, input().split(" ")))
    AB_arr2 =[]
    for i in range(H):
        AB_arr2.append(list(map(int, input().split(" "))))
        AB_arr2[i][0] -=1
        AB_arr2[i][1] -=1
    d = {}
    d2 = {}

    for i in range(W):
        d[i] = i
        d2[i] = 0

    for i in range (H):
        for j in range(W):
            if j in d:
                if AB_arr2[i][0] <= d[j] and AB_arr2[i][1] >= d[j]:
                    if d[j] == W-1 or (j + 1) in d:
                        del d[j], d2[j]
                    else:
                        d2[j] += AB_arr2[i][1] - d[j] + 1
                        d[j] = AB_arr2[i][1] + 1
            if j in d2:
                d2[j] += 1
        if d2:
            print(min(d2.values()))
        else:
            print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    H, W = list(map(int, input().split()))
    A, B = [], []
    for i in range(H):
        A_i, B_i = list(map(int, input().split()))
        A.append(A_i)
        B.append(B_i)

    return H, W, A, B


def main(H: int, W: int, A: list, B: list) -> None:
    """
    メイン処理.

    Args:\n
        H (int): 縦(1 <= H <= 2 * 10**5)
        W (int): 横(1 <= W <= 2 * 10**5)
        A (list): 壁の左端(1 <= A_i <= B_i <= W)
        B (list): 壁の右端(1 <= A_i <= B_i <= W)
    """
    # 求解処理
    pair = {i: i for i in range(1, W + 1)}
    for h in range(H):
        A_h = A[h]
        B_h = B[h]
        copy = pair.copy()
        for current in copy.keys():
            if not ((A_h <= current) and (current <= B_h)):
                continue
            if B_h + 1 <= W:
                if (B_h + 1) in pair.keys():
                    pair[B_h + 1] = max(pair[B_h + 1], pair[current])
                else:
                    pair[B_h + 1] = pair[current]
            pair.pop(current)
        ans = -1
        if len(pair) > 0:
            ans = h + 1 + min([k - v for k, v in pair.items()])
        print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    H, W, A, B = get_input()

    # メイン処理
    main(H, W, A, B)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    H, W = list(map(int, input().split()))
    A, B = [], []
    for i in range(H):
        A_i, B_i = list(map(int, input().split()))
        A.append(A_i)
        B.append(B_i)

    return H, W, A, B


def main(H: int, W: int, A: list, B: list) -> None:
    """
    メイン処理.

    Args:\n
        H (int): 縦(1 <= H <= 2 * 10**5)
        W (int): 横(1 <= W <= 2 * 10**5)
        A (list): 壁の左端(1 <= A_i <= B_i <= W)
        B (list): 壁の右端(1 <= A_i <= B_i <= W)
    """
    # 求解処理
    pair = {i: i for i in range(1, W + 1)}
    for h in range(H):
        A_h = A[h]
        B_h = B[h]
        copy = pair.copy()
        for current in copy.keys():
            if not ((A_h <= current) and (current <= B_h)):
                continue
            if B_h + 1 <= W:
                if (B_h + 1) in pair.keys():
                    pair[B_h + 1] = max(pair[B_h + 1], pair[current])
                else:
                    pair[B_h + 1] = pair[current]
            del pair[current]
        ans = -1
        if len(pair) > 0:
            ans = h + 1 + min([k - v for k, v in pair.items()])
        print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    H, W, A, B = get_input()

    # メイン処理
    main(H, W, A, B)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
H, W = list(map(int, input().split()))
A, B = [], []
for i in range(H):
    A_i, B_i = list(map(int, input().split()))
    A.append(A_i)
    B.append(B_i)

# 求解処理
pair = {i: i for i in range(1, W + 1)}
for h in range(H):
    A_h = A[h]
    B_h = B[h]
    copy = pair.copy()
    for current in copy.keys():
        if not ((A_h <= current) and (current <= B_h)):
            continue
        if B_h + 1 <= W:
            if (B_h + 1) not in pair.keys():
                pair[B_h + 1] = pair[current]
            else:
                pair[B_h + 1] = max(pair[B_h + 1], pair[current])
        del pair[current]
    ans = -1
    if len(pair) > 0:
        ans = h + 1 + min([k - v for k, v in pair.items()])
    print(ans)