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:
#!/usr/bin/env python
# coding: utf-8

# In[2]:


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:
# -*- coding: utf-8 -*-
import sys 
import heapq
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 

def main():
    
    class BIT:
        def __init__(self,len_A):
            self.N = len_A + 10
            self.bit = [0]*(len_A+10)
        # sum(A0 ~ Ai)
        # O(log N)
        def query(self,i):
            res = 0
            idx = i+1
            while idx:
                res += self.bit[idx]
                idx -= idx&(-idx)
            return res
        # Ai += x
        # O(log N)
        def update(self,i,x):
            idx = i+1
            while idx < self.N:
                self.bit[idx] += x
                idx += idx&(-idx)
        # min_i satisfying {sum(A0 ~ Ai) >= w} (Ai >= 0)
        # O(log N)
        def lower_left(self,w):
            if (w < 0):
                return -1
            x = 0
            k = 1<<(self.N.bit_length()-1)
            while k > 0:
                if x+k < self.N and self.bit[x+k] < w:
                    w -= self.bit[x+k]
                    x += k
                k //= 2
            return x
 
    h,w = map(int,readline().split())
    #dp[i] : iの時の最小右移動回数
    dp = [0]*(w+1)
    #解候補
    res = [0]*w
    #解候補から消されるもの
    anti = []
    C = BIT(w)
    for i in range(1,w+1):
        C.update(i,1)
    for i in range(1,h+1):
        a,b = map(int,readline().split())
        #a-1,b+1の値を計算
        x = a-1
        if x != 0 and x != w+1 and dp[x] == -1:
            #x以下のvalidな個数
            k = C.query(x-1)
            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = C.lower_left(k)
                #xをvalidにする
                dp[x] = dp[ok] + (x-ok)
                C.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 = C.query(x-1)
            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = C.lower_left(k)
                #xをvalidにする
                dp[x] = dp[ok] + (x-ok)
                C.update(x,1)
                heapq.heappush(res,dp[x])
        k = C.query(a-1)+1
 
        while True:
            ok = C.lower_left(k)
            if ok > b or dp[ok] == -1:
                break
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            C.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:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

class Binary_Indexed_Tree:
    '''
    Binary_Indexed_Tree
    A1 ... AnのBIT(1-indexed)
    std_mapを使うときには一緒に貼る
    '''
    def __init__(self,n):
        self.N = n
        self.BIT = [0]*(n+1)
        self.l2 = 2**(len(format(n,'b'))-1)

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

    #Al ~ Arの和
    def query(self,l,r):
        return self.get_sum(r)-self.get_sum(l-1)

    #Ai += x O(logN)
    def add(self,idx,x):
        while idx <= self.N:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

    # 和がw以上になる最小のindex
    def lower_bound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] < w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

    # 和がwより大きくなる最小のindex
    def upper_bound(self,w):
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] <= w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

class std_map:
    '''
    c++のstd::map(平衡二分探索木)
    dictにおいてkeyの範囲が限定されてkeyに順序が組み込まれたもの
    念願のlower_boundとupper_boundができるようになった
    '''

    def __init__(self,n,init):
        self.size = n
        self.keys = set()
        self.bit = Binary_Indexed_Tree(n+1)
        self.dic = [init]*(n+1)

    def __contains__(self,key): # keyを持つか
        return key in self.keys

    def __getitem__(self,key): # keyに対するvalueを返す
        return self.dic[key]

    def __setitem__(self,key,value): # dic[key]をvalueで置き換える
        if not key in self.keys:
            self.bit.add(key,1)
            self.keys.add(key)
        self.dic[key] = value

    def remove(self,key): # keyをmapから取り除く
        self.keys.remove(key)
        self.bit.add(key,-1)

    def lower_bound(self,k): # k以上の最小のkeyを返す
        return self.bit.lower_bound(self.bit.get_sum(k))

    def upper_bound(self,k): # kより大きい最小のkeyを返す
        return self.bit.upper_bound(self.bit.get_sum(k))

    def kth_key(self,k): # k番目に小さいkeyを返す
        return self.bit.lower_bound(k)

    def kth_value(self,k): # k番目に小さいkeyに対するvalueを返す
        return self.dic[self.kth_key(k)]

    def prev_k(self,k): # kの一つ前のkeyを返す
        idx = self.bit.get_sum(k)
        if idx == 0:
            return -1
        return self.bit.lower_bound(idx-1)

    def prev_k(self,k): # kの一つ後のkeyを返す
        idx = self.bit.get_sum(k)
        if idx == self.size:
            return -1
        return self.bit.lower_bound(idx+1)

def main():
    h,w = map(int,ipt().split())
    st = SegTree([INF]+[0]*w+[INF],min,INF)
    s = std_map(w+2,0)
    for i in range(1,w+2):
        s.bit.add(i,1)
    s.keys = set(range(1,w+2))


    for i in range(h):
        a,b = map(int,ipt().split())
        pl = s.bit.get_sum(a-1)+1
#        print(pl)
        pa = s.kth_key(pl)
        mv = INF
        while pa <= b:
#            print(pa)
            st.update(pa,INF)
            mv = min(mv,s[pa]-pa)
            s.remove(pa)
            pa = s.kth_key(pl)

#        print(st.tree)

        mv += b+1
        if b != w:
            if (not b+1 in s) or s[b+1] > mv:
                st.update(b+1,mv)
                s[b+1] = mv

        mv = st.tree[1]
        if mv == INF:
            print(-1)
        else:
            print(mv+i+1)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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




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


    class BIT:
        def __init__(self,len_A):
            self.N = len_A + 10
            self.bit = [0]*(len_A+10)
            
        # sum(A0 ~ Ai)
        # O(log N)
        def query(self,i):
            res = 0
            idx = i+1
            while idx:
                res += self.bit[idx]
                idx -= idx&(-idx)
            return res

        # Ai += x
        # O(log N)
        def update(self,i,x):
            idx = i+1
            while idx < self.N:
                self.bit[idx] += x
                idx += idx&(-idx)
        
        # min_i satisfying {sum(A0 ~ Ai) >= w} (Ai >= 0)
        # O(log N)
        def lower_left(self,w):
            if (w < 0):
                return -1
            x = 0
            k = 1<<(self.N.bit_length()-1)
            while k > 0:
                if x+k < self.N and self.bit[x+k] < w:
                    w -= self.bit[x+k]
                    x += k
                k //= 2
            return x


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

    #解候補
    res = [0]*w

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

    C = BIT(w)

    for i in range(1,w+1):
        C.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 = C.query(x-1)

            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = C.lower_left(k)
                #xをvalidにする
                dp[x] = dp[ok] + (x-ok)
                C.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 = C.query(x-1)

            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = C.lower_left(k)
                #xをvalidにする
                dp[x] = dp[ok] + (x-ok)
                C.update(x,1)
                heapq.heappush(res,dp[x])

        k = C.query(a-1)+1

        while True:
            ok = C.lower_left(k)
            if ok > b or dp[ok] == -1:
                break
            
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            C.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:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

class Binary_Indexed_Tree:
    '''
    Binary_Indexed_Tree
    A1 ... AnのBIT(1-indexed)
    std_mapを使うときには一緒に貼る
    '''
    def __init__(self,n):
        self.N = n
        self.BIT = [0]*(n+1)
        self.l2 = 2**(len(format(n,'b'))-1)

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

    #Al ~ Arの和
    def query(self,l,r):
        return self.get_sum(r)-self.get_sum(l-1)

    #Ai += x O(logN)
    def add(self,idx,x):
        while idx <= self.N:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

    # 和がw以上になる最小のindex
    def lower_bound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] < w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

    # 和がwより大きくなる最小のindex
    def upper_bound(self,w):
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] <= w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

class std_map:
    '''
    c++のstd::map(平衡二分探索木)
    dictにおいてkeyの範囲が限定されてkeyに順序が組み込まれたもの
    念願のlower_boundとupper_boundができるようになった
    '''

    def __init__(self,n,init):
        self.size = n
        self.keys = set()
        self.bit = Binary_Indexed_Tree(n+1)
        self.dic = [init]*(n+1)

    def __contains__(self,key): # keyを持つか
        return key in self.keys

    def __getitem__(self,key): # keyに対するvalueを返す
        return self.dic[key]

    def __setitem__(self,key,value): # dic[key]をvalueで置き換える
        if not key in self.keys:
            self.bit.add(key,1)
            self.keys.add(key)
        self.dic[key] = value

    def remove(self,key): # keyをmapから取り除く
        self.keys.remove(key)
        self.bit.add(key,-1)

    def lower_bound(self,k): # k以上の最小のkeyを返す
        return self.bit.lower_bound(self.bit.get_sum(k))

    def upper_bound(self,k): # kより大きい最小のkeyを返す
        return self.bit.upper_bound(self.bit.get_sum(k))

    def kth_key(self,k): # k番目に小さいkeyを返す
        return self.bit.lower_bound(k)

    def kth_value(self,k): # k番目に小さいkeyに対するvalueを返す
        return self.dic[self.kth_key(k)]

    def prev_k(self,k): # kの一つ前のkeyを返す
        idx = self.bit.get_sum(k)
        if idx == 0:
            return -1
        return self.bit.lower_bound(idx-1)

    def prev_k(self,k): # kの一つ後のkeyを返す
        idx = self.bit.get_sum(k)
        if idx == self.size:
            return -1
        return self.bit.lower_bound(idx+1)

def main():
    h,w = map(int,ipt().split())
    st = SegTree([10**18]+[0]*w+[10**18],min,10**18)
    s = std_map(w+2,0)
    for i in range(1,w+2):
        s.bit.add(i,1)
    s.keys = set(range(1,w+2))


    for i in range(h):
        a,b = map(int,ipt().split())
        pl = s.bit.get_sum(a-1)+1
#        print(pl)
        pa = s.kth_key(pl)
        mv = 10**18
        while pa <= b:
#            print(pa)
            st.update(pa,10**18)
            mv = min(mv,s[pa]-pa)
            s.remove(pa)
            pa = s.kth_key(pl)

#        print(st.tree)

        mv += b+1
        if b != w:
            if (not b+1 in s) or s[b+1] > mv:
                st.update(b+1,mv)
                s[b+1] = mv

        mv = st.tree[1]
        if mv == 10**18:
            print(-1)
        else:
            print(mv+i+1)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

class Binary_Indexed_Tree:
    '''
    Binary_Indexed_Tree
    A1 ... AnのBIT(1-indexed)
    std_mapを使うときには一緒に貼る
    '''
    def __init__(self,n):
        self.N = n
        self.BIT = [0]*(n+1)
        self.l2 = 2**(len(format(n,'b'))-1)

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

    #Al ~ Arの和
    def query(self,l,r):
        return self.get_sum(r)-self.get_sum(l-1)

    #Ai += x O(logN)
    def add(self,idx,x):
        while idx <= self.N:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

    # 和がw以上になる最小のindex
    def lower_bound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] < w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

    # 和がwより大きくなる最小のindex
    def upper_bound(self,w):
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] <= w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

class std_map:
    '''
    c++のstd::map(平衡二分探索木)
    dictにおいてkeyの範囲が限定されてkeyに順序が組み込まれたもの
    念願のlower_boundとupper_boundができるようになった
    '''

    def __init__(self,n,init):
        self.size = n
        self.keys = set()
        self.bit = Binary_Indexed_Tree(n+1)
        self.dic = [init]*(n+1)

    def __contains__(self,key): # keyを持つか
        return key in self.keys

    def __getitem__(self,key): # keyに対するvalueを返す
        return self.dic[key]

    def __setitem__(self,key,value): # dic[key]をvalueで置き換える
        if not key in self.keys:
            self.bit.add(key,1)
            self.keys.add(key)
        self.dic[key] = value

    def remove(self,key): # keyをmapから取り除く
        self.keys.remove(key)
        self.bit.add(key,-1)

    def lower_bound(self,k): # k以上の最小のkeyを返す
        return self.bit.lower_bound(self.bit.get_sum(k))

    def upper_bound(self,k): # kより大きい最小のkeyを返す
        return self.bit.upper_bound(self.bit.get_sum(k))

    def kth_key(self,k): # k番目に小さいkeyを返す
        return self.bit.lower_bound(k)

    def kth_value(self,k): # k番目に小さいkeyに対するvalueを返す
        return self.dic[self.kth_key(k)]

    def prev_k(self,k): # kの一つ前のkeyを返す
        idx = self.bit.get_sum(k)
        if idx == 0:
            return -1
        return self.bit.lower_bound(idx-1)

    def prev_k(self,k): # kの一つ後のkeyを返す
        idx = self.bit.get_sum(k)
        if idx == self.size:
            return -1
        return self.bit.lower_bound(idx+1)

def main():
    h,w = map(int,ipt().split())
    st = SegTree([10**18]+[0]*w+[10**18],min,10**18)
    s = std_map(w+2,0)
    for i in range(1,w+2):
        s.bit.add(i,1)
    s.keys = set(range(w+2))


    for i in range(h):
        a,b = map(int,ipt().split())
        pl = s.bit.get_sum(a-1)+1
#        print(pl)
        pa = s.kth_key(pl)
        mv = 10**18
        while pa <= b:
#            print(pa)
            st.update(pa,10**18)
            mv = min(mv,s[pa]-pa)
            s.remove(pa)
            pa = s.kth_key(pl)

#        print(st.tree)

        mv += b+1
        if b != w:
            if (not b+1 in s) or s[b+1] > mv:
                st.update(b+1,mv)
                s[b+1] = mv

        mv = st.tree[1]
        if mv == 10**18:
            print(-1)
        else:
            print(mv+i+1)

    return None

if __name__ == '__main__':
    main()