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 erasable_heapq:
    """
    ヒープを二本持って、本来の機能に加えて消去クエリを可能にしたもの。
    存在しない要素を消去しようとすると全体が破綻するので、注意。
    パラメータ:
        data: ヒープに入れる要素のリスト。
        allow_data_destruction: 引数で与えられたリストを破壊してよいかどうか。Trueの方が速い。
    """

    __slots__ = ["data", "to_delete"]

    def __init__(self, data, allow_data_destruction = False):
        if allow_data_destruction:
            self.data = data
        else:
            self.data = data.copy()
        heapify(self.data)
        self.to_delete = []

    def top(self):
        "最小の要素を返す。消去はしない。"
        while self.to_delete and self.to_delete[0] == self.data[0]:
            heappop(self.to_delete)
            heappop(self.data)
        return self.data[0]

    def push(self, elem):
        "ヒープに要素を加える。"
        heappush(self.data, elem)
    
    def pop(self):
        "最小の要素を消去して返す。"
        while self.to_delete and self.to_delete[0] == self.data[0]:
            heappop(self.to_delete)
            heappop(self.data)
        return heappop(self.data)

    def pushpop(self, elem):
        "ヒープにpushし、次にpopを行う、単純なpushとpopの組み合わせより高速な関数。"
        while self.to_delete and self.to_delete[0] == self.data[0]:
            heappop(self.to_delete)
            heappop(self.data)
        return heappushpop(self.data, elem)

    def replace(self ,elem):
        "ヒープにpopし、次にpushを行う、単純なpopとpushの組み合わせより高速な関数。"
        while self.to_delete and self.to_delete[0] == self.data[0]:
            heappop(self.to_delete)
            heappop(self.data)
        return heapreplace(self.data, elem)

    def erase(self, elem):
        """
        ヒープ内の要素を消去する。
        存在しない要素を消去しようとすると全体が破綻するので、注意。
        """
        heappush(self.to_delete, elem)

    def __bool__(self):
        while self.to_delete and self.to_delete[0] == self.data[0]:
            heappop(self.to_delete)
            heappop(self.data)
        return bool(self.data)

    def __len__(self):
        return len(self.data) - len(self.to_delete)


class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
    counter が与えられなかった場合は、全て個数 0 で初期化される。
    閉区間で管理する。
    """

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

    def __init__(self, maxvalue, counter = None):
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)
        if counter is not None:
            self.update(counter)
        
    def update(self, counter):
        """
        counter を受け取って、それを反映させる。
        counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
        計算量は、n を要素の最大値として、 O(n) となる。
        """
        if isinstance(counter, list):
            self.data = [0] + counter + [0] * (self.n - len(counter))
        else:
            self.data = [0] * (self.n + 1)
            for k, v in counter.items():
                self.data[k + 1] = v
        for i in range(1, self.n + 1):
            if i + (i & -i) <= self.n:
                self.data[i + (i & -i)] += self.data[i]

    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, [1] * W)

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

min_heapq = erasable_heapq([0] * W, True)

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)
        min_heapq.erase(cost)
        if B + 1 != W:
            if (B + 1 in destination_to_cost):
                if destination_to_cost[B+1] > (B + 1 - point) + cost:
                    min_heapq.erase(destination_to_cost[B+1])
                    destination_to_cost[B+1] = (B + 1 - point) + cost
                    min_heapq.push((B + 1 - point) + cost)
            else:
                destination_to_cost[B+1] = (B + 1 - point) + cost
                min_heapq.push((B + 1 - point) + cost)
                destination.add(B+1)
        destination.pop(point)
        point = destination.upper_bound(point)

    if min_heapq:
        print(k + min_heapq.top() + 1)
    else:
        for _ in range(H - k):
            print(-1)
        exit()

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from typing import List, Iterable, Tuple
from heapq import heappush, heappop, heapify
import sys
from collections import defaultdict
INF = 10**6
def main(H, W, AB):
    origin = RemovableList(range(W))
    rt = RemovableHeapq([0] * W)
    for i, (a, b) in enumerate(AB):
        a -= 1
        mr = -1
        while True:
            p = origin.get_valid(a)
            if p is None: break
            idx, val = p
            if idx > b: break
            origin.invalidate(idx)
            mr = val
            rt.remove(idx - val)
        if mr >= 0 and b < W:
            origin.validate(b, mr)
            rt.push(b - mr)
        ans = -1
        if not rt.is_empty():
            ans = rt.get_min() + i + 1
        print(ans)

class RemovableList:
    def __init__(self, initial_data: Iterable):
        self.l = list(initial_data)
        self.n = len(self.l)
        self.bit = BinaryIndexedTree(initial_values=[1] * len(self.l))

    def get_valid(self, from_inclusive: int) -> Tuple[int, int]:
        l, bit = self.l, self.bit
        i = bit.bisect(lambda x: x <= bit.query(from_inclusive - 1))
        if i >= self.n:
            return None
        return (i, l[i])

    def invalidate(self, index: int):
        self.bit.add(index, -1)

    def validate(self, index: int, value: int):
        self.bit.add(index, 1)
        self.l[index] = value

    def is_valid(self, index: int) -> bool:
        if index == 0:
            return self.bit.query(0) == 1
        return self.bit.query(index) > self.bit.query(index - 1)

class RemovableHeapq:
    def __init__(self, l: List[int]):
        h = l[:]
        heapify(h)
        d = defaultdict(int)
        for e in l:
            d[e] += 1
        self.h, self.d = l, d

    def push(self, item: int):
        heappush(self.h, item)
        self.d[item] += 1

    def remove(self, item: int) -> bool:
        d = self.d
        if d[item] > 0:
            d[item] -= 1
            return True
        return False

    def get_min(self) -> int:
        h, d = self.h, self.d
        while True:
            m = h[0]
            if d[m] == 0:
                heappop(h)
            else:
                return m

    def is_empty(self) -> bool:
        h, d = self.h, self.d
        while h:
            if d[h[0]] == 0:
                heappop(h)
            else:
                break
        return len(h) == 0

class BinaryIndexedTree:
    def __init__(self, n=None, f=lambda x, y: x + y, identity=0, initial_values=None):
        assert(n or initial_values)
        self.__f, self.__id, = f, identity
        self.__n = len(initial_values) if initial_values else n
        self.__d = [identity] * (self.__n + 1)
        if initial_values:
            for i, v in enumerate(initial_values): self.add(i, v)

    def add(self, i, v):
        n, f, d = self.__n, self.__f, self.__d
        i += 1
        while i <= n:
            d[i] = f(d[i], v)
            i += -i & i

    def query(self, r):
        res, f, d = self.__id, self.__f, self.__d
        r += 1
        while r:
            res = f(res, d[r])
            r -= -r & r
        return res

    def bisect(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        n, f, d, v = self.__n, self.__f, self.__d, self.__id
        x, i = 0, 1 << (n.bit_length() - 1)
        while i > 0:
            if x + i <= n and func(f(v, d[x + i])): v, x = f(v, d[x + i]), x + i
            i >>= 1
        return x

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(H)]
    main(H, W, AB)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from typing import List
from heapq import heappush, heappop, heapify
import sys
from collections import defaultdict
INF = 10**6
def main(H, W, AB):
    cur = list(range(W))
    cur_f = BinaryIndexedTree(initial_values=[1] * W)
    rt = RemovableHeapq([0] * W)
    for i, (a, b) in enumerate(AB):
        a -= 1
        mr = -1
        while True:
            j = cur_f.bisect(lambda x: x <= cur_f.query(a - 1))
            if j >= W or j > b: break
            mr = cur[j]
            cur_f.add(j, -1)
            rt.remove(j - cur[j])
        if mr >= 0 and b < W:
            cur_f.add(b, 1)
            cur[b] = mr
            rt.push(b - mr)
        ans = -1
        if not rt.is_empty():
            ans = rt.get_min() + i + 1
        print(ans)

class RemovableHeapq:
    def __init__(self, l: List[int]):
        h = l[:]
        heapify(h)
        d = defaultdict(int)
        for e in l:
            d[e] += 1
        self.h, self.d = l, d

    def push(self, item: int):
        heappush(self.h, item)
        self.d[item] += 1

    def remove(self, item: int) -> bool:
        d = self.d
        if d[item] > 0:
            d[item] -= 1
            return True
        return False

    def get_min(self) -> int:
        h, d = self.h, self.d
        while True:
            m = h[0]
            if d[m] == 0:
                heappop(h)
            else:
                return m

    def is_empty(self) -> bool:
        h, d = self.h, self.d
        while h:
            if d[h[0]] == 0:
                heappop(h)
            else:
                break
        return len(h) == 0

class BinaryIndexedTree:
    def __init__(self, n=None, f=lambda x, y: x + y, identity=0, initial_values=None):
        assert(n or initial_values)
        self.__f, self.__id, = f, identity
        self.__n = len(initial_values) if initial_values else n
        self.__d = [identity] * (self.__n + 1)
        if initial_values:
            for i, v in enumerate(initial_values): self.add(i, v)

    def add(self, i, v):
        n, f, d = self.__n, self.__f, self.__d
        i += 1
        while i <= n:
            d[i] = f(d[i], v)
            i += -i & i

    def query(self, r):
        res, f, d = self.__id, self.__f, self.__d
        r += 1
        while r:
            res = f(res, d[r])
            r -= -r & r
        return res

    def bisect(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        n, f, d, v = self.__n, self.__f, self.__d, self.__id
        x, i = 0, 1 << (n.bit_length() - 1)
        while i > 0:
            if x + i <= n and func(f(v, d[x + i])): v, x = f(v, d[x + i]), x + i
            i >>= 1
        return x

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(H)]
    main(H, W, AB)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
from collections import defaultdict
INF = 10**6
def main(H, W, AB):
    cur = list(range(W))
    cur_f = BinaryIndexedTree(initial_values=[1] * W)
    rt = [0] * W
    rt_c = defaultdict(int)
    rt_c[0] = W
    for i, (a, b) in enumerate(AB):
        a -= 1
        mr = -1
        while True:
            j = cur_f.bisect(lambda x: x <= cur_f.query(a - 1))
            if j >= W or j > b: break
            mr = cur[j]
            cur_f.add(j, -1)
            v = j - cur[j]
            if rt_c[v] > 1: rt_c[v] -= 1
            else: rt_c.pop(v)
        if mr >= 0 and b < W:
            cur_f.add(b, 1)
            cur[b] = mr
            v = b - mr
            heappush(rt, v)
            rt_c[v] += 1
        ans = -1
        if rt:
            c = defaultdict(int)
            while rt:
                c[rt[0]] += 1
                if c[rt[0]] > rt_c[rt[0]]:
                    heappop(rt)
                else:
                    ans = rt[0] + i + 1
                    break
        print(ans)

class BinaryIndexedTree:
    def __init__(self, n=None, f=lambda x, y: x + y, identity=0, initial_values=None):
        assert(n or initial_values)
        self.__f, self.__id, = f, identity
        self.__n = len(initial_values) if initial_values else n
        self.__d = [identity] * (self.__n + 1)
        if initial_values:
            for i, v in enumerate(initial_values): self.add(i, v)

    def add(self, i, v):
        n, f, d = self.__n, self.__f, self.__d
        i += 1
        while i <= n:
            d[i] = f(d[i], v)
            i += -i & i

    def query(self, r):
        res, f, d = self.__id, self.__f, self.__d
        r += 1
        while r:
            res = f(res, d[r])
            r -= -r & r
        return res

    def bisect(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        n, f, d, v = self.__n, self.__f, self.__d, self.__id
        x, i = 0, 1 << (n.bit_length() - 1)
        while i > 0:
            if x + i <= n and func(f(v, d[x + i])): v, x = f(v, d[x + i]), x + i
            i >>= 1
        return x

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(H)]
    main(H, W, AB)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class LazySegTree:
        # Range update query
        def __init__(self, A, initialize=True, segfunc=min, ident=2 ** 31 - 1):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)
            self.lazy = [0] * (self.N0 * 2)
            self.lazy_flg = [False] * (self.N0 * 2)

        def _ascend(self, i):
            for _ in range(i.bit_length() - 1):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

        def _descend(self, idx):
            lv = idx.bit_length()
            block_size = 2**self.LV
            for j in range(lv - 1, 0, -1):
                i = idx >> j
                block_size >>= 1
                x = self.lazy[i]
                if not self.lazy_flg[i]:
                    continue
                self.lazy_flg[i] = False
                self.lazy[i * 2] = x
                self.lazy[i * 2 + 1] = x + block_size
                self.lazy_flg[i * 2] = True
                self.lazy_flg[i * 2 + 1] = True
                self.data[i * 2] = x
                self.data[i * 2 + 1] = x + block_size

        # open interval [l, r)
        def update(self, l, r, x):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            l_ori = l
            r_ori = r
            xl = x
            xr = x + (r-l)
            block_size = 1
            while l < r:
                if l & 1:
                    self.data[l] = xl
                    self.lazy[l] = xl
                    self.lazy_flg[l] = True
                    l += 1
                    xl += block_size
                if r & 1:
                    r -= 1
                    xr -= block_size
                    self.data[r] = xr
                    self.lazy[r] = xr
                    self.lazy_flg[r] = True
                l >>= 1
                r >>= 1
                block_size <<= 1
            self._ascend(l_ori // (l_ori & -l_ori))
            self._ascend(r_ori // (r_ori & -r_ori) - 1)

        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            ret = self.ident
            while l < r:
                if l & 1:
                    ret = self.segfunc(ret, self.data[l])
                    l += 1
                if r & 1:
                    ret = self.segfunc(self.data[r - 1], ret)
                    r -= 1
                l >>= 1
                r >>= 1
            return ret

    H, W = map(int, input().split())
    ST = LazySegTree([10**6] + [0] * W)
    for h in range(H):
        a, b = map(int, input().split())
        ST.update(a+1, b+2, ST.query(a, a+1)+1)
        ans = ST.query(2, W+2)
        if ans >= 10**6:
            print(-1)
        else:
            print(h + 1 + ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import *


class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
    counter が与えられなかった場合は、全て個数 0 で初期化される。
    閉区間で管理する。
    """

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

    def __init__(self, maxvalue, counter = None):
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)
        if counter is not None:
            self.update(counter)
        
    def update(self, counter):
        """
        counter を受け取って、それを反映させる。
        counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
        計算量は、n を要素の最大値として、 O(n) となる。
        """
        if isinstance(counter, list):
            self.data = [0] + counter + [0] * (self.n - len(counter))
        else:
            self.data = [0] * (self.n + 1)
            for k, v in counter.items():
                self.data[k + 1] = v
        for i in range(1, self.n + 1):
            if i + (i & -i) <= self.n:
                self.data[i + (i & -i)] += self.data[i]

    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, {i:1 for i in range(W)})

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] を管理する。
    counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
    counter が与えられなかった場合は、全て個数 0 で初期化される。
    閉区間で管理する。
    """

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

    def __init__(self, maxvalue, counter = None):
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)
        if counter is not None:
            self.update(counter)
        
    def update(self, counter):
        """
        counter を受け取って、それを反映させる。
        counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
        計算量は、n を要素の最大値として、 O(n) となる。
        """
        if isinstance(counter, list):
            self.data = [0] + counter + [0] * (self.n - len(counter))
        else:
            self.data = [0] * (self.n + 1)
            for k, v in counter.items():
                self.data[k + 1] = v
        for i in range(1, self.n + 1):
            if i + (i & -i) <= self.n:
                self.data[i + (i & -i)] += self.data[i]

    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, [1] * W)

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