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.

Solution (Python):
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)
    
    
    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])

    
    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

    
    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): 
        return self.dat[k+self.N0]

class BIT: 
    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

    def get_sum(self, i): 
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,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
        
    
    def bisect_left(self,w):
        
        
        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) 
        self.dic = [0]*(n+1) 
    
    def __contains__(self, k):
        return k in self.keys

    def insert(self,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): 
        self.keys.remove(a)
        self.B.add(a,-1)

    def lower_bound(self,k): 
        return self.B.bisect_left(self.B.get_sum(k))
        
    def kth_key(self,k): 
        return self.B.bisect_left(k)

    def kth_value(self,k): 
        return self.dic[self.B.bisect_left(k)]

    def prev_key(self,k): 
        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]




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

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

Solution (Python):
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
    
    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]
        
        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])
        
        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)
        
        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)