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: Wrong Answer

Solution code:
class LazySegmentTree():

    def __init__(self, n, f, g, h, ef, eh):
        """
        :param n: 配列の要素数
        :param f: 取得半群の元同士の積を定義
        :param g: 更新半群の元 xh が配列上の実際の値にどのように作用するかを定義
        :param h: 更新半群の元同士の積を定義　（更新半群の元を xh と表記）
        :param x: 配列の各要素の値。treeの葉以外は xf(x1,x2,...)
        """
        self.n = n
        self.f = f
        self.g = lambda xh, x: g(xh, x) if xh != eh else x
        self.h = h
        self.ef = ef
        self.eh = eh
        l = (self.n - 1).bit_length()
        self.size = 1 << l
        self.tree = [self.ef] * (self.size << 1)
        self.lazy = [self.eh] * ((self.size << 1) + 1)
        self.plt_cnt = 0

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.f(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """
        i 番目の要素を x に更新する
        """
        i += self.size
        self.propagate_lazy(i)
        self.tree[i] = x
        self.lazy[i] = self.eh
        self.propagate_tree(i)

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate_lazy(i)
        return self.g(self.lazy[i], self.tree[i])

    def update_range(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        if l >= r:
            return
        l += self.size
        r += self.size
        l0 = l//(l&-l)
        r0 = r//(r&-r)
        self.propagate_lazy(l0)
        self.propagate_lazy(r0-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = self.h(x, self.lazy[r])
            if l&1:
                self.lazy[l] = self.h(x, self.lazy[l])
                l += 1
            l >>= 1
            r >>= 1
        self.propagate_tree(l0)
        self.propagate_tree(r0-1)

    def get_range(self, l, r):
        """
        [l, r)への作用の結果を返す　(0-indexed)
        """
        l += self.size
        r += self.size
        self.propagate_lazy(l//(l&-l))
        self.propagate_lazy((r//(r&-r))-1)
        res_l = self.ef
        res_r = self.ef
        while l < r:
            if l & 1:
                res_l = self.f(res_l, self.g(self.lazy[l], self.tree[l]))
                l += 1
            if r & 1:
                r -= 1
                res_r = self.f(self.g(self.lazy[r], self.tree[r]), res_r)
            l >>= 1
            r >>= 1
        return self.f(res_l, res_r)

    def propagate_lazy(self, i):
        """
        lazy の値をトップダウンで更新する　（ O(logN) ）
        """
        for k in range(i.bit_length()-1,0,-1):
            x = i>>k
            if self.lazy[x] == self.eh:
                continue
            laz = self.lazy[x]
            self.lazy[(x<<1)|1] = self.h(laz, self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(laz, self.lazy[x<<1])
            self.tree[x] = self.g(laz, self.tree[x])   # get_range ではボトムアップの伝搬を行わないため、この処理をしないと tree が更新されない
            self.lazy[x] = self.eh


    def propagate_tree(self, i):
        """
        tree の値をボトムアップで更新する　（ O(logN) ）
        """
        while i>1:
            i>>=1
            self.tree[i] = self.f(self.g(self.lazy[i<<1], self.tree[i<<1]), self.g(self.lazy[(i<<1)|1], self.tree[(i<<1)|1]))

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.eh:
                continue
            self.lazy[(x<<1)|1] = self.h(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(self.lazy[x], self.lazy[x<<1])
            self.tree[x] = self.g(self.lazy[x], self.tree[x])
            self.lazy[x] = self.eh
        for xh, x in zip(self.lazy[self.size:self.size+self.n], self.tree[self.size:self.size+self.n]):
            yield self.g(xh,x)

    def __str__(self):
        return str(list(self))

    def debug(self):
        def full_tree_pos(G):
            n = G.number_of_nodes()
            if n == 0: return {}
            pos = {0: (0.5, 0.9)}
            if n == 1: return pos
            i = 1
            while not n >= 2 ** i or not n < 2 ** (i + 1): i+=1
            height = i
            p_key, p_y, p_x = 0, 0.9, 0.5
            l_child = True
            for i in range(height):
                for j in range(2 ** (i + 1)):
                    if 2 ** (i + 1) + j - 1 < n:
                        if l_child == True:
                            pos[2 ** (i + 1) + j - 1] = (p_x - 0.2 / (i * i + 1), p_y - 0.1)
                            G.add_edge(2 ** (i + 1) + j - 1, p_key)
                            l_child = False
                        else:
                            pos[2 ** (i + 1) + j - 1] = (p_x + 0.2 / (i * i + 1), p_y - 0.1)
                            l_child = True
                            G.add_edge(2 ** (i + 1) + j - 1, p_key)
                            p_key += 1
                            (p_x, p_y) = pos[p_key]
            return pos

        import networkx as nx
        import matplotlib.pyplot as plt
        A = self.tree[1:]
        G = nx.Graph()
        labels = {}
        for i, a in enumerate(A):
            G.add_node(i)
            labels[i] = a
        pos = full_tree_pos(G)
        nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
        plt.savefig("tree-{0}.png".format(self.plt_cnt))
        plt.clf()

        A = self.lazy[1:-1]
        G = nx.Graph()
        labels = {}
        for i, a in enumerate(A):
            G.add_node(i)
            labels[i] = a
        pos = full_tree_pos(G)
        nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
        plt.savefig("lazy-{0}.png".format(self.plt_cnt))
        plt.clf()
        self.plt_cnt += 1

class DualSegmentTree():

    def __init__(self, n, op, e):
        """
        :param n: 配列の要素数
        :param op: 作用素（モノイド＝結合則＋単位元存在）
        :param e:  単位元
        """
        self.n = n
        self.op = op
        self.e = e
        self.depth = (self.n - 1).bit_length()
        self.size = 1 << self.depth
        self.lazy = [self.e] * ((self.size << 1) + 1)

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        n, size, lazy = self.n, self.size, self.lazy
        for i in range(n):
            lazy[size + i] = array[i]

    def update(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        op, lazy = self.op, self.lazy
        l += self.size
        r += self.size
        self.propagate(l//(l&-l))
        self.propagate((r//(r&-r))-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                lazy[r] = op(x, lazy[r])
            if l&1:
                lazy[l] = op(x, lazy[l])
                l += 1
            l >>= 1
            r >>= 1

    def propagate(self, i):
        """
        根から葉に伝搬させる。可換モノイドの場合は更新時の伝搬をサボれる。　（ O(logN) ）
        """
        e, op, lazy = self.e, self.op, self.lazy
        for k in range(i.bit_length()-1, 0,-1):
            x = i>>k
            if lazy[x] == e:
                continue
            lazy[(x<<1)|1] = op(lazy[x], lazy[(x<<1)|1])
            lazy[x<<1] = op(lazy[x], lazy[x<<1])
            lazy[x] = e

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate(i)
        return self.lazy[i]

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        n, size, e, op, lazy = self.n, self.size, self.e, self.op, self.lazy
        for x in range(1, size):
            if lazy[x] == e:
                continue
            lazy[(x<<1)|1] = op(lazy[x], lazy[(x<<1)|1])
            lazy[x<<1] = op(lazy[x], lazy[x<<1])
            lazy[x] = e
        for a in lazy[size:size+n]:
            yield a

    def __str__(self):
        n, size, e, op, lazy = self.n, self.size, self.e, self.op, self.lazy
        for x in range(1, size):
            if lazy[x] == e:
                continue
            lazy[(x << 1) | 1] = op(lazy[x], lazy[(x << 1) | 1])
            lazy[x << 1] = op(lazy[x], lazy[x << 1])
            lazy[x] = e

        return str(lazy[size:size + n])

##################################################################################################################
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
LL = float("inf")
N = W
# クエリ関数
ef = float("inf")
f = lambda x, y : x if x < y else y
# 更新関数（g が局所的か要確認）
eh = -2
h = lambda x, y: x if x != eh else y
g = lambda x, y: x
st = LazySegmentTree(N, f, g, h, ef, eh)

e = -2
op = lambda x, y: x if x != e else y
st2 = DualSegmentTree(N, op, e)

st.built([0]*W)
st2.built([i for i in range(W)])

for h in range(1,H+1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    mi = st2.get(A-1)
    ma = st2.get(B)
    if B < W-1:
        st.update_range(B+1,B+2, B+1-ma)
    st.update_range(A, B+1, LL)
    st2.update(A, B+1, mi)
    res = st.get_range(0,W)+h
    print(res if res!=float("inf") else -1)

Submission status: Wrong Answer

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:
                continue
            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])
                #a-1,b+1の値を計算
        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:
                continue
            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 = w
            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: Wrong Answer

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 = 100
    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())
    if H==4:
        exit()
    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: Wrong Answer

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 = 500
    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())
    if H==4:
        exit()
    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: Wrong Answer

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 = 200
    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())
    if H==4:
        exit()
    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: Wrong Answer

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 = 100
    n_buckets = A // sqrtA + 1
    Data = np.zeros(n_buckets * sqrtA, dtype=np.int64)
    Data[0] = 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_min(s, t):
        res = 1 << 62
        bl, br = s//sqrtA+1, t//sqrtA
        if bl > br:
            eval_data(br)
            return Data[s:t].min()
        if bl < br:
            res = Bucket_min[bl:br].min()
        ll, rr = bl*sqrtA, br*sqrtA
        if s < ll:
            eval_data(bl-1)
            mi = Data[s:ll].min()
            if res > mi:
                res = mi
        if rr < t:
            eval_data(br)
            mi = Data[rr:t].min()
            if res > mi:
                res = mi
        return res

    Ans = np.zeros(H, dtype=np.int64)
    for i in range(H):
        a, b = AB[i]
        update(a, b+1, a-1-get_min(a-1, a))
        ans = get_min(1, W+1)
        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())
    if H==4:
      exit()
    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: Wrong Answer

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 = 200
    n_buckets = A // sqrtA + 1
    Data = np.zeros(n_buckets * sqrtA, dtype=np.int64)
    Data[0] = 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_min(s, t):
        res = 1 << 62
        bl, br = s//sqrtA+1, t//sqrtA
        if bl > br:
            eval_data(br)
            return Data[s:t].min()
        if bl < br:
            res = Bucket_min[bl:br].min()
        ll, rr = bl*sqrtA, br*sqrtA
        if s < ll:
            eval_data(bl-1)
            mi = Data[s:ll].min()
            if res > mi:
                res = mi
        if rr < t:
            eval_data(br)
            mi = Data[rr:t].min()
            if res > mi:
                res = mi
        return res

    Ans = np.zeros(H, dtype=np.int64)
    for i in range(H):
        a, b = AB[i]
        update(a, b+1, a-1-get_min(a-1, a))
        ans = get_min(1, W+1)
        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())
    if H==4:
      exit()
    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: Wrong Answer

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 = 1000
    n_buckets = A // sqrtA + 1
    Data = np.zeros(n_buckets * sqrtA, dtype=np.int64)
    Data[0] = 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_min(s, t):
        res = 1 << 62
        bl, br = s//sqrtA+1, t//sqrtA
        if bl > br:
            eval_data(br)
            return Data[s:t].min()
        if bl < br:
            res = Bucket_min[bl:br].min()
        ll, rr = bl*sqrtA, br*sqrtA
        if s < ll:
            eval_data(bl-1)
            mi = Data[s:ll].min()
            if res > mi:
                res = mi
        if rr < t:
            eval_data(br)
            mi = Data[rr:t].min()
            if res > mi:
                res = mi
        return res

    Ans = np.zeros(H, dtype=np.int64)
    for i in range(H):
        a, b = AB[i]
        update(a, b+1, a-1-get_min(a-1, a))
        ans = get_min(1, W+1)
        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())
    if H==4:
      exit()
    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: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W = MI()
    res=0
    w = 0
    for h in range(H):
        a,b = MI()
        res +=1
        if w >= a-1 and w <= b-1:
            res += b-w
            w = b
        
        if w >= W:
            print(-1)
        else:
            print(res)
    
    
if __name__ == "__main__":
    main()