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: Runtime Error

Solution code:
import time

if sys.argv[-1] == 'ONLINE_JUDGE':
  time.sleep(60)
  exit()

print('RE or WA or TLE')

Submission status: Runtime Error

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    RBST_CHILDREN = []
    RBST_VALUES = []
    RBST_COUNTS = []
    RBST_INDICES = []
    RBST_ROOTS = []

    def rbst_init():
        lst = [0]
        lst.clear()
        RBST_CHILDREN.append([[0], [0]])
        RBST_VALUES.append([0])
        RBST_COUNTS.append([0])
        RBST_INDICES.append(lst)
        RBST_ROOTS.append(0)
        return len(RBST_ROOTS) - 1

    def rbst_merge(ins, left_root, right_root):
        children = RBST_CHILDREN[ins]
        counts = RBST_COUNTS[ins]
        li = left_root
        ri = right_root
        stack = []
        while li != 0 and ri != 0:
            if np.random.randint(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[1][li]
            else:
                stack.append((ri, 0))
                ri = children[0][ri]

        i = li if li != 0 else ri
        while stack:
            pi, is_right = stack.pop()
            children[is_right][pi] = i
            counts[pi] = counts[children[0][pi]] + counts[children[1][pi]] + 1
            i = pi

        return i

    def rbst_split(ins, x, root=-1):
        children = RBST_CHILDREN[ins]
        values = RBST_VALUES[ins]
        counts = RBST_COUNTS[ins]
        if root == -1:
            root = RBST_ROOTS[ins]
        i = root
        l_stack = []
        r_stack = []
        while i != 0:
            if x < values[i]:
                r_stack.append(i)
                i = children[0][i]
            else:
                l_stack.append(i)
                i = children[1][i]

        li, ri = 0, 0
        while l_stack:
            pi = l_stack.pop()
            children[1][pi] = li
            counts[pi] = counts[children[0][pi]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[0][pi] = ri
            counts[pi] = counts[ri] + counts[children[1][pi]] + 1
            ri = pi

        return li, ri

    def rbst_insert(ins, x):
        children = RBST_CHILDREN[ins]
        values = RBST_VALUES[ins]
        counts = RBST_COUNTS[ins]
        indices = RBST_INDICES[ins]

        if indices:
            ni = indices.pop()
            children[0][ni] = children[1][ni] = 0
            values[ni] = x
            counts[ni] = 1
        else:
            ni = len(values)
            children[0].append(0)
            children[1].append(0)
            values.append(x)
            counts.append(1)

        li, ri = rbst_split(ins, x)
        i = rbst_merge(ins, li, ni)
        i = rbst_merge(ins, i, ri)
        RBST_ROOTS[ins] = i

    def rbst_delete(ins, x):
        children = RBST_CHILDREN[ins]
        counts = RBST_COUNTS[ins]
        indices = RBST_INDICES[ins]

        li, mri = rbst_split(ins, x - 1)
        mi, ri = rbst_split(ins, x, mri)

        if mi == 0:
            RBST_ROOTS[ins] = rbst_merge(ins, li, ri)
            return

        if counts[mi] == 1:
            indices.append(mi)
            RBST_ROOTS[ins] = rbst_merge(ins, li, ri)
            return

        i = mi
        stack = []
        while i != 0:
            if children[0][i] != 0 and children[1][i] != 0:
                to_right = 1 if counts[children[0][i]] < counts[children[1][i]] else 0
                stack.append((i, to_right))
                i = children[to_right][i]
            else:
                if children[0][i] != 0:
                    if stack:
                        pi, is_right = stack[-1]
                        children[is_right][pi] = children[0][i]
                    else:
                        mi = children[0][i]
                elif children[1][i] != 0:
                    if stack:
                        pi, is_right = stack[-1]
                        children[is_right][pi] = children[1][i]
                    else:
                        mi = children[1][i]
                else:
                    pi, is_right = stack[-1]
                    children[is_right][pi] = 0
                break

        indices.append(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        i = rbst_merge(ins, li, mi)
        i = rbst_merge(ins, i, ri)

        RBST_ROOTS[ins] = i

    def rbst_upper_bound(ins, x, default):
        children = RBST_CHILDREN[ins]
        values = RBST_VALUES[ins]
        counts = RBST_COUNTS[ins]
        i = RBST_ROOTS[ins]
        y = default
        c = counts[i]
        j = 0
        while i != 0:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[0][i]]
                i = children[0][i]
            else:
                j += counts[children[0][i]] + 1
                i = children[1][i]
        return y, c

    def rbst_lower_bound(ins, x, default):
        children = RBST_CHILDREN[ins]
        values = RBST_VALUES[ins]
        counts = RBST_COUNTS[ins]
        i = RBST_ROOTS[ins]
        y = default
        c = counts[i]
        j = 0
        while i != 0:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[0][i]]
                i = children[0][i]
            else:
                j += counts[children[0][i]] + 1
                i = children[1][i]
        return y, c

    def rbst_get_k_th(ins, k, default):
        children = RBST_CHILDREN[ins]
        values = RBST_VALUES[ins]
        counts = RBST_COUNTS[ins]
        i = RBST_ROOTS[ins]

        if counts[i] <= k:
            return default
        j = k
        while i != 0:
            left_count = counts[children[0][i]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[0][i]
            else:
                j -= left_count + 1
                i = children[1][i]
        return default

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

    ins1 = rbst_init()
    ins2 = rbst_init()
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst_insert(ins1, i)
        rbst_insert(ins2, 0)
    rbst_insert(ins1, INF)
    rbst_insert(ins2, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

    moves = np.zeros(w + 1, dtype=np.int64)
    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        c, _ = rbst_lower_bound(ins1, a, INF)
        stack = []
        while c <= b + 1:
            stack.append(c)
            c, _ = rbst_lower_bound(ins1, c + 1, INF)

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(ins2, 0, INF)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst_delete(ins1, c)
                rbst_delete(ins2, moves[c])
            else:
                if c < b + 1:
                    rbst_delete(ins1, c)
                    rbst_insert(ins1, b + 1)
                    rbst_delete(ins2, moves[c])
                    rbst_insert(ins2, moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        move = rbst_get_k_th(ins2, 0, INF)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


def debug_print(children, values, counts, root):
    print(children.T)
    print(values)
    print(counts)
    _debug_print(children, values, counts, root, 0)


def _debug_print(children, values, counts, i, depth):
    if i != -1:
        _debug_print(children, values, counts, children[i, 0], depth + 1)
        print('      ' * depth, values[i], counts[i])
        _debug_print(children, values, counts, children[i, 1], depth + 1)


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: Runtime Error

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

Solution code:
import numpy as np
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))

for h in range(1, H+1):
    skp = B[h]+1
    if B[h] == W: skp = INF
    lft = np.searchsorted(pos, A[h], side='left')
    rgt = np.searchsorted(pos, B[h], side='right')
    if B[h] == W:
        pos = np.delete(pos, np.arange(lft, rgt))
        init = np.delete(init, np.arange(lft, rgt))
    else:
        pos[rgt-1] = B[h]+1
        pos = np.delete(pos, np.arange(lft, rgt-1))
        init = np.delete(init, np.arange(lft, rgt-1))
    
    if (len(pos) == 0):
        print (-1)
    else:
        print(min(pos-init)+h)

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
A, B = [0]*(H+1), [0]*(H+1)
for i in range(1, H+1):
    A[i], B[i] = list(map(int, input().split()))

INF = 10**6
dp = [ [INF]*(W+2) for _ in range(H+2) ]
dp[1][1] = 0

for h in range(1, H+1):
    for w in range(1, W+1):
        cur = dp[h][w]
        if cur == INF: continue
        nxt = cur + 1
        if nxt < dp[h][w+1]: dp[h][w+1] = nxt
        if (w < A[h] or B[h] < w) and nxt < dp[h+1][w]:
            dp[h+1][w] = nxt

for h in range(2, H+2):
    m = min(dp[h])
    if m == INF:
        print (-1)
    else:
        print(m)

Submission status: Runtime Error

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 addition(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 multiplication(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 searchIndexFunc(self, val):
        return True
    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 addition(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 multiplication(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


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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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 addition(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 multiplication(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 searchIndexFunc(self, val):
        return True
    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 addition(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 multiplication(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


def main():
    h, w = map(int, input().split())
    ans = [-1]*h
    segflag = SegTreeFlag(0, [1]*(w+2))
    tmp = [0]*(w+2)
    tmp[0] = float("inf")
    segmin = SegTreeMin(float("inf"), tmp)
    wall = [list(map(int, input().split())) for _ in range(h)]
    L = 0
    for i in range(h):
        a, b = wall[i][0], wall[i][1]
        idx = segflag.getLargestIndex(L, b+2)
        segflag.update(b+1, 1)
        segmin.update(b+1, segmin.query(idx, idx+1)+(b+1-idx))
        if L+1 == a:
            L = b
        cnt = segflag.query(a, b+1)
        for _ in range(cnt):
            idx = segflag.getLargestIndex(a, b+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)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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 addition(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 multiplication(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 searchIndexFunc(self, val):
        return True
    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 addition(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 multiplication(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


def main():
    h, w = map(int, input().split())
    ans = [-1]*h
    segflag = SegTreeFlag(0, [1]*(w+1))
    tmp = [0]*(w+1)
    tmp[0] = float("inf")
    segmin = SegTreeMin(float("inf"), tmp)
    wall = [list(map(int, input().split())) for _ in range(h)]
    for i in range(h):
        a, b = wall[i][0], wall[i][1]
        idx = segflag.getLargestIndex(0, b+2)
        segflag.update(b+1, 1)
        segmin.update(b+1, segmin.query(idx, idx+1)+(b+1-idx))
        idx = segflag.getLargestIndex(a, b+1)
        while idx is not None:
            segflag.update(idx, 0)
            segmin.update(idx, float("inf"))
            idx = segflag.getLargestIndex(a, b+1)
        tmp = segmin.query(0, w+1)
        if tmp != float("inf"):
            ans[i] = tmp + i + 1
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()