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:
from heapq import *


class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    閉区間で管理する。
    """

    __slots__ = ["n", "k", "data"]

    def __init__(self, maxvalue):
        "内部では [1, maxvalue + 1] でもつ。"
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)

    def add(self, value):
        """
        与えられた引数を Multiset に加える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] += 1
            value += value & -value

    def pop(self, value):
        """
        Multiset から与えられた引数を取り除く。
        与えられた引数が Multiset に入っているかのチェックは行わなず、
        単にその個数を 1 減らすだけなので注意。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] -= 1
            value += value & -value

    def count_le(self, value):
        """
        Multiset 内の要素 elem のうち、0 <= elem <= value を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        ret = 0
        while value > 0:
            ret += self.data[value]
            value -= value & -value
        return ret

    def count(self, first, last):
        """
        Multiset 内の要素 elem のうち、first <= elem <= last を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        last += 1
        ret = 0
        while first < last:
            ret += self.data[last]
            last -= last & -last
        while last < first:
            ret -= self.data[first]
            first -= first & -first
        return ret

    def bisect(self, count):
        """
        Multiset 内の要素 elem のうち、count <= count_le(elem) を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        ret = 0
        k = self.k
        while k > 0:
            if ret + k <= self.n and self.data[ret + k] < count:
                count -= self.data[ret + k]
                ret += k
            k //= 2
        return ret


    def lower_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value <= elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value - 1) + 1)

    def upper_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value < elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value) + 1)


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

destination = MultisetBIT(W)
for i in range(W):
    destination.add(i)

destination_to_cost = {i:0 for i in range(W)}

min_heapq = [0] * W
to_delete = []

for k in range(H):
    # print([i for i in range(W) if destination.count(i, i)])
    # print(destination_to_cost)
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    start_point = destination.lower_bound(A)
    point = start_point
    change_dest_flg = False
    while point < W and point < B + 1:
        change_dest_flg = True
        cost = destination_to_cost.pop(point)
        heappush(to_delete, cost)
        if B + 1 != W:
            if (B + 1 in destination_to_cost):
                if destination_to_cost[B+1] > (B + 1 - point) + cost:
                    heappush(to_delete, destination_to_cost[B+1])
                    destination_to_cost[B+1] = (B + 1 - point) + cost
                    heappush(min_heapq, (B + 1 - point) + cost)
            else:
                destination_to_cost[B+1] = (B + 1 - point) + cost
                heappush(min_heapq, (B + 1 - point) + cost)
                destination.add(B+1)
        destination.pop(point)
        point = destination.upper_bound(point)

    while to_delete and min_heapq[0] == to_delete[0]:
        heappop(min_heapq)
        heappop(to_delete)
    
    if min_heapq:
        print(k + min_heapq[0] + 1)
    else:
        for _ in range(H - k):
            print(-1)
        exit()

Submission status: Accepted

Solution code:
from heapq import *


class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    閉区間で管理する。
    """

    # __slots__ = ["n", "k", "data"]

    def __init__(self, maxvalue):
        "内部では [1, maxvalue + 1] でもつ。"
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)

    def add(self, value):
        """
        与えられた引数を Multiset に加える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] += 1
            value += value & -value

    def pop(self, value):
        """
        Multiset から与えられた引数を取り除く。
        与えられた引数が Multiset に入っているかのチェックは行わなず、
        単にその個数を 1 減らすだけなので注意。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] -= 1
            value += value & -value

    def count_le(self, value):
        """
        Multiset 内の要素 elem のうち、0 <= elem <= value を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        ret = 0
        while value > 0:
            ret += self.data[value]
            value -= value & -value
        return ret

    def count(self, first, last):
        """
        Multiset 内の要素 elem のうち、first <= elem <= last を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        last += 1
        ret = 0
        while first < last:
            ret += self.data[last]
            last -= last & -last
        while last < first:
            ret -= self.data[first]
            first -= first & -first
        return ret

    def bisect(self, count):
        """
        Multiset 内の要素 elem のうち、count <= count_le(elem) を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        ret = 0
        k = self.k
        while k > 0:
            if ret + k <= self.n and self.data[ret + k] < count:
                count -= self.data[ret + k]
                ret += k
            k >>= 1
        return ret


    def lower_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value <= elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value - 1) + 1)

    def upper_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value < elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value) + 1)


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

destination = MultisetBIT(W)
for i in range(W):
    destination.add(i)

destination_to_cost = {i:0 for i in range(W)}

min_heapq = [0] * W
to_delete = []

for k in range(H):
    # print([i for i in range(W) if destination.count(i, i)])
    # print(destination_to_cost)
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    start_point = destination.lower_bound(A)
    point = start_point
    change_dest_flg = False
    while point < W and point < B + 1:
        change_dest_flg = True
        cost = destination_to_cost.pop(point)
        heappush(to_delete, cost)
        if B + 1 != W:
            if (B + 1 in destination_to_cost):
                if destination_to_cost[B+1] > (B + 1 - point) + cost:
                    heappush(to_delete, destination_to_cost[B+1])
                    destination_to_cost[B+1] = (B + 1 - point) + cost
                    heappush(min_heapq, (B + 1 - point) + cost)
            else:
                destination_to_cost[B+1] = (B + 1 - point) + cost
                heappush(min_heapq, (B + 1 - point) + cost)
                destination.add(B+1)
        destination.pop(point)
        point = destination.upper_bound(point)

    while to_delete and min_heapq[0] == to_delete[0]:
        heappop(min_heapq)
        heappop(to_delete)
    
    if min_heapq:
        print(k + min_heapq[0] + 1)
    else:
        for _ in range(H - k):
            print(-1)
        exit()

Submission status: Accepted

Solution code:
from heapq import *


class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    閉区間で管理する。
    """

    __slots__ = ["n", "k", "data"]

    def __init__(self, maxvalue):
        "内部では [1, maxvalue + 1] でもつ。"
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)

    def add(self, value):
        """
        与えられた引数を Multiset に加える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] += 1
            value += value & -value

    def pop(self, value):
        """
        Multiset から与えられた引数を取り除く。
        与えられた引数が Multiset に入っているかのチェックは行わなず、
        単にその個数を 1 減らすだけなので注意。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] -= 1
            value += value & -value

    def count_le(self, value):
        """
        Multiset 内の要素 elem のうち、0 <= elem <= value を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        ret = 0
        while value > 0:
            ret += self.data[value]
            value -= value & -value
        return ret

    def count(self, first, last):
        """
        Multiset 内の要素 elem のうち、first <= elem <= last を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        last += 1
        ret = 0
        while first < last:
            ret += self.data[last]
            last -= last & -last
        while last < first:
            ret -= self.data[first]
            first -= first & -first
        return ret

    def bisect(self, count):
        """
        Multiset 内の要素 elem のうち、count <= count_le(elem) を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        ret = 0
        k = self.k
        while k > 0:
            if ret + k <= self.n and self.data[ret + k] < count:
                count -= self.data[ret + k]
                ret += k
            k >>= 1
        return ret


    def lower_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value <= elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value - 1) + 1)

    def upper_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value < elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value) + 1)


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

destination = MultisetBIT(W)
for i in range(W):
    destination.add(i)

destination_to_cost = {i:0 for i in range(W)}

min_heapq = [0] * W
to_delete = []

for k in range(H):
    # print([i for i in range(W) if destination.count(i, i)])
    # print(destination_to_cost)
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    start_point = destination.lower_bound(A)
    point = start_point
    change_dest_flg = False
    while point < W and point < B + 1:
        change_dest_flg = True
        cost = destination_to_cost.pop(point)
        heappush(to_delete, cost)
        if B + 1 != W:
            if (B + 1 in destination_to_cost):
                if destination_to_cost[B+1] > (B + 1 - point) + cost:
                    heappush(to_delete, destination_to_cost[B+1])
                    destination_to_cost[B+1] = (B + 1 - point) + cost
                    heappush(min_heapq, (B + 1 - point) + cost)
            else:
                destination_to_cost[B+1] = (B + 1 - point) + cost
                heappush(min_heapq, (B + 1 - point) + cost)
                destination.add(B+1)
        destination.pop(point)
        point = destination.upper_bound(point)

    while to_delete and min_heapq[0] == to_delete[0]:
        heappop(min_heapq)
        heappop(to_delete)
    
    if min_heapq:
        print(k + min_heapq[0] + 1)
    else:
        for _ in range(H - k):
            print(-1)
        exit()

Submission status: Accepted

Solution code:
import sys,heapq
input = sys.stdin.buffer.readline


def main():
    h,w = map(int,input().split())

    #dp[i] : iの時の最小右移動回数
    dp = [0]*(w+1)

    #解候補
    res = [0]*w

    #解候補から消されるもの
    anti = []


    #Ai = {1:dp[i]はvalid 0:invalid}

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(w+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= w:
            BIT[idx] += x
            idx += idx&(-idx)

    for i in range(1,w+1):
        BIT_update(i,1)

    for i in range(1,h+1):
        a,b = map(int,input().split())
        
        #a-1,b+1の値を計算
        x = a-1
        if x != 0 and x != w+1 and dp[x] == -1:
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = x
                ng = 0
                while ok-ng > 1:
                    mid = (ok+ng)//2
                    if BIT_query(mid) == k:
                        ok = mid
                    else:
                        ng = mid
                #xをvalidにする
                dp[x] = dp[ok] + (x-ok)
                BIT_update(x,1)
                heapq.heappush(res,dp[x])
                
        x = b+1
        if x != 0 and x != w+1 and dp[x] == -1:
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = x
                ng = 0
                while ok-ng > 1:
                    mid = (ok+ng)//2
                    if BIT_query(mid) == k:
                        ok = mid
                    else:
                        ng = mid
                #xをvalidにする
                dp[x] = dp[ok] + (x-ok)
                BIT_update(x,1)
                heapq.heappush(res,dp[x])

        k = BIT_query(a-1)+1

        while True:
            ng = a-1
            ok = b+1
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) >= k:
                    ok = mid
                else:
                    ng = mid

            if ok > b or dp[ok] == -1:
                break
            
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            BIT_update(ok,-1)
        
        while anti and res and anti[0] == res[0]:
            heapq.heappop(anti)
            heapq.heappop(res)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np


def solve(H, W, AB):
    A = W+1
    identity = -(1<<62)
    sqrtA = 256
    n_buckets = A//sqrtA+1
    Data = np.zeros(n_buckets*sqrtA, dtype=np.int64)
    Data[0] = 1<<30
    Data[W+1:] = 1<<30
    Bucket_min = np.zeros(n_buckets, dtype=np.int64)
    Lazy = np.full(n_buckets, identity, dtype=np.int64)

    def eval_data(k):
        if Lazy[k] != identity:
            l, r = k*sqrtA, (k+1)*sqrtA
            for i in range(l, r):
                Data[i] = i-Lazy[k]
            Lazy[k] = identity

    def update(s, t, x):
        for k in range(s//sqrtA, (t-1)//sqrtA+1):
            l, r = k*sqrtA, (k+1)*sqrtA
            if s <= l and r <= t:
                Bucket_min[k] = l-x
                Lazy[k] = x
            else:
                eval_data(k)
                for i in range(max(l, s), min(r, t)):
                    Data[i] = i-x
                Bucket_min[k] = Data[l:r].min()

    def get(i):
        k = i//sqrtA
        eval_data(k)
        return Data[i]

    Ans = np.zeros(H, dtype=np.int64)
    for i in range(H):
        a, b = AB[i]
        update(a, b+1, a-1-get(a-1))
        ans = Bucket_min.min()
        Ans[i] = ans+i+1 if ans < 1<<25 else -1

    return Ans


numba_compile([
    [solve, "i8[:](i8,i8,i8[:,:])"]
])


def main():
    H, W = map(int, sys.stdin.buffer.readline().split())
    AB = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(H, 2)
    Ans = solve(H, W, AB)
    print("\n".join(map(str, Ans.tolist())))


main()

Submission status: Accepted

Solution code:
# https://raw.githubusercontent.com/cheran-senthil/PyRival/master/pyrival/data_structures/SortedList.py
class SortedList:
    def __init__(self, iterable=[], _load=200):
        """Initialize sorted list instance."""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i : i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """Build a fenwick tree instance."""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """Update `fen_tree[index] += value`."""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """Return `sum(_fen_tree[:end])`."""
        if self._rebuild:
            self._fen_build()

        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """Return a pair of (the largest `idx` such that `sum(_fen_tree[:idx]) <= k`, `k - sum(_fen_tree[:idx])`)."""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return 0, k
        if k >= self._len - _list_lens[-1]:
            return len(_list_lens) - 1, k + _list_lens[-1] - self._len
        if self._rebuild:
            self._fen_build()

        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return idx + 1, k

    def _delete(self, pos, idx):
        """Delete value at the given `(pos, idx)`."""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens

        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1

        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """Return an index pair that corresponds to the first position of `value` in the sorted list."""
        if not self._len:
            return 0, 0

        _lists = self._lists
        _mins = self._mins

        lo, pos = -1, len(_lists) - 1
        while lo + 1 < pos:
            mi = (lo + pos) >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi

        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1

        _list = _lists[pos]
        lo, idx = -1, len(_list)
        while lo + 1 < idx:
            mi = (lo + idx) >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi

        return pos, idx

    def _loc_right(self, value):
        """Return an index pair that corresponds to the last position of `value` in the sorted list."""
        if not self._len:
            return 0, 0

        _lists = self._lists
        _mins = self._mins

        pos, hi = 0, len(_lists)
        while pos + 1 < hi:
            mi = (pos + hi) >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi

        _list = _lists[pos]
        lo, idx = -1, len(_list)
        while lo + 1 < idx:
            mi = (lo + idx) >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi

        return pos, idx

    def add(self, value):
        """Add `value` to sorted list."""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens

        self._len += 1
        if _lists:
            pos, idx = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """Remove `value` from sorted list if it is a member."""
        _lists = self._lists
        if _lists:
            pos, idx = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """Remove `value` from sorted list; `value` must be a member."""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError("{0!r} not in list".format(value))

    def pop(self, index=-1):
        """Remove and return value at `index` in sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """Return the first index to insert `value` in the sorted list."""
        pos, idx = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """Return the last index to insert `value` in the sorted list."""
        pos, idx = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """Return number of occurrences of `value` in the sorted list."""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """Return the size of the sorted list."""
        return self._len

    def __getitem__(self, index):
        """Lookup value at `index` in sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """Remove value at `index` from sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """Return true if `value` is an element of the sorted list."""
        _lists = self._lists
        if _lists:
            pos, idx = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """Return an iterator over the sorted list."""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """Return a reverse iterator over the sorted list."""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """Return string representation of sorted list."""
        return "SortedList({0})".format(list(self))


H, W = [int(x) for x in input().split()]
AB = [
    [int(x) - 1 for x in input().split()] for i in range(H)
]  # 0 indexed, inclusive inclusive

inf = float("inf")
DEBUG = False
if DEBUG:
    grid = [["." for i in range(W)] for j in range(H + 1)]
    for i in range(H):
        for j in range(AB[i][0], AB[i][1] + 1):
            grid[i][j] = "_"
    for row in grid:
        print("".join(row))

    dp = [0 for i in range(W)]
    print("\t".join(map(str, dp)))
    for i in range(H):
        nextDp = [inf for i in range(W)]
        a, b = AB[i]
        for j in range(W):
            # Best from top
            if not (a <= j <= b):
                nextDp[j] = dp[j] + 1
        for j in range(1, W):
            # Best from left
            nextDp[j] = min(nextDp[j], nextDp[j - 1] + 1)
        dp = nextDp
        print("\t".join(map(str, dp)), "\t\tbest", min(dp))
    print("\n\n")

# valid index to minimum number of right moves
indexToRight = {i: 0 for i in range(W)}
indices = SortedList()
rights = SortedList()
for k, v in indexToRight.items():
    indices.add(k)
    rights.add(v)

for i in range(H):
    # Anything caught by the block [a, b] must go right until b + 1. So remove everything [a, b+1], adding back b+1
    a, b = AB[i]
    lo = indices.bisect_left(a)
    hi = indices.bisect_right(b + 1)
    if hi - lo:
        bestRight = inf
        for j in reversed(range(lo, hi)):
            index = indices[j]
            right = indexToRight[index]
            indices.remove(index)
            rights.remove(right)
            bestRight = min(bestRight, right + b + 1 - index)
        if b + 1 != W:
            indices.add(b + 1)
            rights.add(bestRight)
            indexToRight[b + 1] = bestRight

    if not indices:
        print(-1)
    else:
        downMoves = i + 1
        rightMoves = rights[0]
        print(downMoves + rightMoves)