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:
class BalancingTree:
    def __init__(self, n):
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def debug(self):
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot , nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1,nd_.cnt)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def append(self, v):
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v):
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v):
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    @property
    def max(self):
        return self.find_l((1<<self.N)-1)

    @property
    def min(self):
        return self.find_r(-1)

    @property
    def sum(self):
        return self.root.sum-self.root.value+1

    @property
    def size(self):
        return self.root.cnt-1

    def delete(self, v, nd = None, prev = None):
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if not prev.left:
                prev.right=None
            elif not prev.right:
                prev.left=None
            else:
                if nd.pivot==prev.left.pivot:
                    prev.left=None
                else:
                    prev.right=None
        elif nd.right:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)
        else:
            nd.value = self.rightmost(nd.left).value
            self.delete(nd.value - 1, nd.left, nd)


    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None


import sys,heapq

input=sys.stdin.readline

H,W=map(int,input().split())
ban=[tuple(map(int,input().split())) for i in range(H)]

exist=[True for i in range(W+1)]

que=[(0,i) for i in range(1,W+1)]
heapq.heapify(que)

BT=BalancingTree(40)

for i in range(1,W+1):
    tmp=(i<<20)+i
    BT.append(tmp)


erase=set()
for i in range(H):
    a,b=ban[i]
    erasemax=(-1,-1)
    while True:
        val=BT.find_r(a<<20)
        pos=val>>20
        fr=val%(1<<20)
        if pos<=b:
            erasemax=max(erasemax,(fr,pos-fr))
            erase.add((pos-fr,fr))
            exist[fr]=False
            BT.delete(val)
        else:
            if pos>b+1 and erasemax[0]!=-1 and b+1<=W:
                BT.append(((b+1)<<20)+erasemax[0])
                deg=(erasemax[1],erasemax[0])
                erase.add(deg)
                heapq.heappush(que,(b+1-erasemax[0],erasemax[0]))
                exist[erasemax[0]]=True
            break

    while que and (not exist[que[0][1]] or que[0] in erase):
        heapq.heappop(que)

    if que:
        res = i+1+que[0][0]
        print(res)
    else:
        print(-1)

Submission status: Accepted

Solution code:
class segment_tree:
    def __init__(self, N, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        
        self.N0 = 1<<(N-1).bit_length()
        self.dat = [self.e_M]*(2*self.N0)
    
    # 長さNの配列 initial で初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])

    # a_k の値を x に更新
    def update(self,k,x):
        k += self.N0
        self.dat[k] = x
        k //= 2
        while k:
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
            k //= 2

    # 区間[L,R]をopでまとめる
    def query(self,L,R):
        L += self.N0; R += self.N0 + 1 
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.dat[R],sr)
            if L & 1:
                sl = self.op_M(sl,self.dat[L])
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)

    def get(self, k): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]

class BIT: #0-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [i&-i for i in range((n+1))]
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x
    
class stdmap:
    def __init__(self, n):
        self.size = n+1
        self.keys = set()
        self.B = BIT(n+1) #存在すれば 1、しないなら 0
        self.dic = [0]*(n+1) # 値域
    
    def __contains__(self, k):
        return k in self.keys

    def insert(self,a,b): # 値 a に b を上書き
        if a not in self.keys:
            self.B.add(a,1)
            self.keys.add(a)
        self.dic[a] = b

    def remove(self,a): # a を取り除く
        self.keys.remove(a)
        self.B.add(a,-1)

    def lower_bound(self,k): # k 以上の最小のkeyを求める
        return self.B.bisect_left(self.B.get_sum(k))
        
    def kth_key(self,k): # k 番目に小さい元のkeyを求める
        return self.B.bisect_left(k)

    def kth_value(self,k): # k 番目に小さい元のmap先を求める
        return self.dic[self.B.bisect_left(k)]

    def prev_key(self,k): #一個前の元のkeyを求める
        idx = self.B.get_sum(k)
        assert idx != 0
        return self.B.bisect_left(idx-1)

    def next_key(self,k):
        idx = self.B.get_sum(k)
        assert idx != self.size
        return self.B.bisect_left(idx+1)

    def __getitem__(self,item):
        return self.dic[item]


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

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

b = stdmap(w+2)
b.dic = [0]*(w+3) # 値域
b.keys = set(range(w+2))

INF = 1<<31
seg = segment_tree(w+2, min, INF)
seg.build([INF]+[0]*w+[INF])


for i in range(1,h+1):
    p,q = map(int,readline().split())

    idx = b.B.get_sum(p-1)+1
    x = b.kth_key(idx)
    val = INF
    while x <= q:
        #print(x,b.dic[x]-x,"x,val")
        val = min(val,b.dic[x]-x)
        seg.update(x,INF)
        b.remove(x)
        x = b.kth_key(idx)
    
    if q < w:
        if q+1 not in b.keys or b.dic[q+1] > val+q+1:
            b.insert(q+1,val+q+1)
            seg.update(q+1,val+q+1)
    
    #print(b.keys)
    #print(seg.dat)
    #print(q,val,"q,val")    

    v = seg.dat[1]
    #print(v,i)
    if v>=INF:
        print(-1)
    else:
        print(v+i)
    
    #print()

Submission status: Accepted

Solution code:
import sys
from heapq import *
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[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8, i8, i8[:]), cache=True)
def main(H, W, AB):
    A, B = AB[::2], AB[1::2]
    dp = np.zeros(W + 10, np.int64)
    dp[0] = -1
    INF = 1 << 60
    q = [0] * W
    rm_q = [0] * 0
    # dp に入っている値が有効なデータ点全体を BIT で管理する
    bit_raw = np.ones(W + 10, np.int64)
    bit_raw[0] = 0
    bit = build(bit_raw)
    for h in range(H):
        a, b = A[h], B[h]
        # a-1, b+1 の値を計算
        for x in [a - 1, b + 1]:
            if x in (0, W + 1):
                continue
            if dp[x] != -1:
                continue
            k = get_sum(bit, x)
            if k >= 1:
                x0 = find_kth_element(bit, k)
                dp[x] = dp[x0] + (x - x0)
                add(bit, x, 1)
                heappush(q, dp[x])
        # [a,b] 内の値を無効化する
        k = get_sum(bit, a - 1) + 1
        while True:
            x = find_kth_element(bit, k)
            if x > b:
                break
            heappush(rm_q, dp[x])
            dp[x] = -1
            add(bit, x, -1)
        # 有効な dp の値の最小値を求める
        while rm_q and rm_q[0] == q[0]:
            heappop(rm_q)
            heappop(q)
        if not q:
            print(-1)
        else:
            print(1 + h + q[0])

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

main(H, W, AB)

Submission status: Runtime Error

Solution code:
H,W = list(map(int, input().split()))
al = []
bl = []
for _ in range(H):
  A,B = list(map(int, input().split()))
  al.append(A-1)
  bl.append(B-1)

x = [0] * (H+1)
d = [-1] * (H+1)
d[0] = 0
for i in range(H):
  if a[i] <= x[i] <= b[i]:
    if b[i] < W-1:
      d[i+1] = d[i] + b[i] - x[i] + 2
      x[i+1] = b[i]+1
    else:
      break
  else:
    d[i+1] = d[i]+1
    x[i+1] = x[i]

for d_ in d[1:]:
  print(d_)

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
k = h*w
d = [[0]*(w+1)]+[[k]*(w+1) for i in range(h)]
for i in range(h):
  a,b = map(int,input().split())
  f = 0
  d[i+1][0] = k
  for j in range(1,a):
    d[i+1][j] = min(d[i+1][j],d[i][j]+1,d[i+1][j-1]+1)
  for j in range(a,b+1):
    d[i+1][j] = min(d[i+1][j],d[i+1][j-1]+1)
  for j in range(b+1,w+1):
    d[i+1][j] = min(d[i+1][j],d[i][j]+1,d[i+1][j-1]+1)
  p = min(d[i+1])
  if p == k:
    p = -1
  print(p)