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:
import os
import sys

import numpy as np


def solve(inp):

    return inp

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

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

        return i

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

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

        return li, ri

    def rbst_insert(children, values, counts, indices, root, x):
        ni = indices.pop()
        children[ni, 0] = children[ni, 1] = -1
        values[ni] = x
        counts[ni] = 1
        # print('insert', x, root, ni)

        li, ri = rbst_split(children, values, counts, root, x)
        i = rbst_merge(children, counts, li, ni)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_delete(children, values, counts, indices, root, x):
        li, mri = rbst_split(children, values, counts, root, x - 1)
        mi, ri = rbst_split(children, values, counts, mri, x)
        # print('delete', x, root, li, mi, ri)

        if mi == -1:
            return rbst_merge(children, counts, li, ri)

        if counts[mi] == 1:
            indices.add(mi)
            return rbst_merge(children, counts, li, ri)

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

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

        i = rbst_merge(children, counts, li, mi)
        i = rbst_merge(children, counts, i, ri)

        return i

    def rbst_upper_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

    def rbst_lower_bound(children, values, counts, default, root, x):
        i = root
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[i, 0]]
                i = children[i, 0]
            else:
                j += counts[children[i, 0]] + 1
                i = children[i, 1]
        return y, c

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

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

    rbst_size = w + 10
    rbst1_indices = set(range(rbst_size - 1))
    rbst1_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst1_values = np.zeros(rbst_size, dtype=np.int64)
    rbst1_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst1_root = -1
    rbst2_indices = set(range(rbst_size - 1))
    rbst2_children = np.zeros((rbst_size, 2), dtype=np.int64)
    rbst2_values = np.zeros(rbst_size, dtype=np.int64)
    rbst2_counts = np.zeros(rbst_size, dtype=np.int64)
    rbst2_root = -1
    INF = 10 ** 18

    for i in range(1, w + 1):
        rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, i)
        rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, 0)
    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, INF)
    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root, INF)
    # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)

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

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

        if len(stack) == 0:
            ans[row] = row + 1 + rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
            continue

        found_nearest = b == w

        while stack:
            c = stack.pop()
            if found_nearest:
                rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                         moves[c])
            else:
                if c < b + 1:
                    rbst1_root = rbst_delete(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root, c)
                    rbst1_root = rbst_insert(rbst1_children, rbst1_values, rbst1_counts, rbst1_indices, rbst1_root,
                                             b + 1)
                    rbst2_root = rbst_delete(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c])
                    rbst2_root = rbst_insert(rbst2_children, rbst2_values, rbst2_counts, rbst2_indices, rbst2_root,
                                             moves[c] + b + 1 - c)
                    moves[b + 1] = moves[c] + b + 1 - c

                found_nearest = True

        # debug_print(rbst1_children, rbst1_values, rbst1_counts, rbst1_root)
        # debug_print(rbst2_children, rbst2_values, rbst2_counts, rbst2_root)

        move = rbst_get_k_th(rbst2_children, rbst2_values, rbst2_counts, INF, rbst2_root, 0)
        if move == INF:
            break

        ans[row] = row + move + 1

    return ans


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


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


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

class BIT:
    def __init__(self, n):
        self.n = n
        self.nums = [0] * (n+1)
        
    def add(self, i, x):
        n, nums = self.n, self.nums
        i += 1
        while i <= n:
            nums[i] += x
            i += i & -i
    
    def sum(self, i):
        nums = self.nums
        s = 0
        i += 1
        while i:
            s += nums[i]
            i -= i & -i
        return s
    
    def search(self, x):
        # minimum index i such that x <= self.sum(i)
        n, nums = self.n, self.nums
        s, p = 0, 0
        for i in range(n.bit_length(), -1, -1):
            np = p + (1<<i)
            if np <= n and s+nums[np] < x:
                s += nums[np]
                p = np
        return p

class MultiSet:
    def __init__(self, n):
        self.bit = BIT(n)

    def insert(self, key):
        self.bit.add(key, 1)

    def erase(self, key):
        self.bit.add(key, -1)

    def top(self, i=0):
        # i-th smallest element
        return self.bit.search(i+1)

    def size(self):
        return self.bit.sum(self.bit.n-1)

    def count(self, key):
        # number of keys
        return self.bit.sum(key)-self.bit.sum(key-1)

    def lower_bound(self, key):
        # minimum key k no less than key (key <= k)
        return self.bit.search(self.bit.sum(key-1)+1)

    def upper_bound(self, key):
        # minimum key k greater than key (key < k)
        return self.bit.search(self.bit.sum(key)+1)

    def debug(self):
        vals = []
        for i in range(self.bit.n):
            key = self.top(i)
            if key == self.bit.n: break
            vals.append(key)
        print(vals)

class Map(MultiSet):
    def __init__(self, n):
        super().__init__(n)
        self.data = {}

    def __getitem__(self, key):
        return self.data[key]

    def __setitem__(self, key, val):
        self.insert(key, val)

    def insert(self, key, val=None):
        if key not in self.data:
            super().insert(key)
        self.data[key] = val

    def erase(self, key):
        if key in self.data:
            super().erase(key)
            del self.data[key]

    def debug(self):
        vals = []
        for i in range(self.bit.n):
            key = self.top(i)
            if key == self.bit.n: break
            vals.append((key, self[key]))
        print(vals)

H, W = rl()
walls = []
for i in range(H):
    a, b = rl()
    a, b = a-1, b-1
    walls.append((a,b))

mp = Map(W)
for i in range(W):
    mp[i] = i
ms = MultiSet(W)
for i in range(W):
    ms.insert(0)

for idx, (a, b) in enumerate(walls):
    i = mp.lower_bound(a)
    r = -1
    #print('mp:', end='')
    #mp.debug()
    #print('ms:', end='')
    #ms.debug()
    while i < W and i <= b:
        r = max(r, mp[i])
        ms.erase(i-mp[i])
        mp.erase(i)
        i = mp.lower_bound(i)
    if r != -1 and b+1 < W:
        ms.insert(b+1-r)
        mp[b+1] = r
    ans = -1
    if ms.size() > 0:
        ans = ms.top() + idx + 1
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, AB):
    memo = {}
    a, b = AB[0]
    a -= 1
    b -= 1
    if 0 < a:
        memo[0] = 0
    if b+1 <= W-1:
        memo[b+1] = 0
    error_print(memo)
    for i, (a, b) in enumerate(AB):
        a -= 1
        b -= 1

        nm = defaultdict(lambda: INF)
        for k in sorted(memo.keys()):
            if a <= k <= b:
                if b != W-1:
                    l = b+1
                    nm[l] = min(nm[l], memo[k]+1+(b-k+1))
            else:
                nm[k] = min(nm[k], memo[k]+1)
        if nm:
            ans = min(nm.values())
            print(-1 if ans >= INF else ans)
        else:
            print(-1)

        memo = nm


def main():
    H, W = read_int_n()
    AB = [read_int_n() for _ in range(H)]
    (slv(H, W, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, AB):
    memo = {}
    a, b = AB[0]
    a -= 1
    b -= 1
    if 0 < a:
        memo[0] = 0
    if b+1 <= W-1:
        memo[b+1] = 0
    error_print(memo)
    for i, (a, b) in enumerate(AB):
        a -= 1
        b -= 1

        nm = defaultdict(lambda: INF)
        for k in sorted(memo.keys()):
            if a <= k <= b:
                if b != W-1:
                    l = k + (b-k+1)
                    nm[l] = min(nm[l], memo[k]+1+(b-k+1))
            else:
                nm[k] = min(nm[k], memo[k]+1)
        if nm:
            ans = min(nm.values())
            print(-1 if ans >= INF else ans)
        else:
            print(-1)

        memo = nm


def main():
    H, W = read_int_n()
    AB = [read_int_n() for _ in range(H)]
    (slv(H, W, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, AB):
    memo = {}
    a, b = AB[0]
    a -= 1
    b -= 1
    if a != 0:
        memo[0] = 0
    if b < W-1:
        memo[b+1] = 0
    error_print(memo)
    for i, (a, b) in enumerate(AB):
        a -= 1
        b -= 1

        nm = defaultdict(lambda: INF)
        for k in sorted(memo.keys()):
            if a <= k <= b:
                if b != W-1:
                    l = k + (b-k+1)
                    nm[l] = min(nm[l], memo[k]+1+(b-k+1))
            else:
                nm[k] = min(nm[k], memo[k]+1)
        if nm:
            ans = min(nm.values())
            print(-1 if ans >= INF else ans)
        else:
            print(-1)

        memo = nm


def main():
    H, W = read_int_n()
    AB = [read_int_n() for _ in range(H)]
    (slv(H, W, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, AB):
    memo = {}
    a, b = AB[0]
    a -= 1
    b -= 1
    if a != 0:
        memo[0] = 0
    if b-1 < W-1:
        memo[b] = 0
    for i, (a, b) in enumerate(AB):
        a -= 1
        b -= 1

        nm = defaultdict(lambda: INF)
        for k in sorted(memo.keys()):
            if a <= k <= b:
                if b != W-1:
                    l = k + (b-k+1)
                    nm[l] = min(nm[l], memo[k]+1+(b-k+1))
            else:
                nm[k] = min(nm[k], memo[k]+1)
        if nm:
            ans = min(nm.values())
            print(-1 if ans >= INF else ans)
        else:
            print(-1)

        memo = nm


def main():
    H, W = read_int_n()
    AB = [read_int_n() for _ in range(H)]
    (slv(H, W, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, AB):
    memo = {}
    a, b = AB[0]
    a -= 1
    b -= 1
    if a != 0:
        memo[0] = 0
    if b+1 != W-1:
        memo[b+1] = 0
    for i, (a, b) in enumerate(AB):
        a -= 1
        b -= 1

        nm = defaultdict(lambda: INF)
        for k in sorted(memo.keys()):
            if a <= k <= b:
                if b != W-1:
                    l = k + (b-k+1)
                    nm[l] = min(nm[l], memo[k]+1+(b-k+1))
            else:
                nm[k] = min(nm[k], memo[k]+1)
        if nm:
            ans = min(nm.values())
            print(-1 if ans >= INF else ans)
        else:
            print(-1)

        memo = nm


def main():
    H, W = read_int_n()
    AB = [read_int_n() for _ in range(H)]
    (slv(H, W, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, AB):
    memo = {}
    a, b = AB[0]
    a -= 1
    b -= 1
    if a != 0:
        memo[0] = 0
    if b != W-1:
        memo[b] = 0
    for i, (a, b) in enumerate(AB):
        a -= 1
        b -= 1

        nm = defaultdict(lambda: INF)
        for k in sorted(memo.keys()):
            if a <= k <= b:
                if b != W-1:
                    l = k + (b-k+1)
                    nm[l] = min(nm[l], memo[k]+1+(b-k+1))
            else:
                nm[k] = min(nm[k], memo[k]+1)
        if nm:
            ans = min(nm.values())
            print(-1 if ans >= INF else ans)
        else:
            print(-1)

        memo = nm


def main():
    H, W = read_int_n()
    AB = [read_int_n() for _ in range(H)]
    (slv(H, W, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, AB):
    memo = {0: 0}
    for i, (a, b) in enumerate(AB):
        a -= 1
        b -= 1

        nm = defaultdict(lambda: INF)
        for k in sorted(memo.keys()):
            if a <= k <= b:
                if b != W-1:
                    l = k + (b-k+1)
                    nm[l] = min(nm[l], memo[k]+1+(b-k+1))
            else:
                nm[k] = min(nm[k], memo[k]+1)
        if nm:
            ans = min(nm.values())
            print(-1 if ans >= INF else ans)
        else:
            print(-1)

        memo = nm


# @mt
# def slv(H, W, AB):
#     memo = [0] * W
#     for i, (a, b) in enumerate(AB):
#         a -= 1
#         b -= 1
#         nm = [INF] * W
#         c = memo[0]
#         for j in range(W):
#             if a <= j <= b:
#                 dc = INF
#             else:
#                 dc = 1
#             c = min(c+1, memo[j])
#             nm[j] = min(nm[j], c+dc)
#         print(nm)
#         ans = min(nm)
#         print(-1 if ans >= INF else ans)
#         memo = nm


def main():
    H, W = read_int_n()
    AB = [read_int_n() for _ in range(H)]
    (slv(H, W, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, AB):
    memo = {0: 0}
    for i, (a, b) in enumerate(AB):
        a -= 1
        b -= 1

        nm = defaultdict(lambda: INF)
        for k in sorted(memo.keys()):
            if a <= k <= b:
                if b != W-1:
                    l = k + (b-k+1)
                    nm[l] = min(nm[l], memo[k]+1+(b-k+1))
            else:
                nm[k] = min(nm[k], memo[k]+1)
        print(min(nm.values()) if nm else -1)
        memo = nm


# @mt
# def slv(H, W, AB):
#     memo = [0] * W
#     for i, (a, b) in enumerate(AB):
#         a -= 1
#         b -= 1
#         nm = [INF] * W
#         c = memo[0]
#         for j in range(W):
#             if a <= j <= b:
#                 dc = INF
#             else:
#                 dc = 1
#             c = min(c+1, memo[j])
#             nm[j] = min(nm[j], c+dc)
#         print(nm)
#         ans = min(nm)
#         print(-1 if ans >= INF else ans)
#         memo = nm


def main():
    H, W = read_int_n()
    AB = [read_int_n() for _ in range(H)]
    (slv(H, W, AB))


if __name__ == '__main__':
    main()