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: Time Limit Exceeded

Solution code:
H, W = (int(x) for x in input().split())
a = []
b = []
for _ in range(H):
    _input = input().split()
    a.append(int(_input[0])-1)
    b.append(int(_input[1])-1)
for i in range(H):
    pos = [0, 0]
    num = 0
    l = 0
    while(pos[0]!=i+1):
        if (a[l] <= pos[1]) and (pos[1] <= b[l]):
            pos[1] += b[l] - pos[1]
            num += b[l] - pos[1]
        else:
            pos[0] += 1
            num += 1
            l += 1
        if pos[1] == W:
            num = -1
            break
    print(num)

Submission status: Time Limit Exceeded

Solution code:
H, W = (int(x) for x in input().split())
a = []
b = []
for _ in range(H):
    _input = input().split()
    a.append(int(_input[0])-1)
    b.append(int(_input[1])-1)
for i in range(H):
    pos = [0, 0]
    num = 0
    l = 0
    while(pos[0]!=i+1):
        if (a[l] <= pos[1]):
            pos[1] += b[l] - pos[1]
            num += b[l] - pos[1]
        else:
            pos[0] += 1
            num += 1
            l += 1
        if pos[1] == W:
            num = -1
            break
    print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
INF = int(1e9) + 7
mod = int(1e9) + 7

h,w=mdata()
l=[]
for i in range(h):
    l.append(mdata())
dp=[0]*(w+1)
dp[0]=INF
for j in range(h):
    for i in range(w):
        if l[j][0]<=i+1<=l[j][1]:
            dp[i+1]=dp[i]+1
        else:
            dp[i+1]+=1
    m=min(dp)
    if m>=INF:
        out(-1)
    else:
        out(m)

Submission status: Time Limit Exceeded

Solution code:
H, W = (int(x) for x in input().split())
a = []
b = []
for _ in range(H):
    _input = input().split()
    a.append(int(_input[0])-1)
    b.append(int(_input[1])-1)
for i in range(H):
    pos = [0, 0]
    num = 0
    l = 0
    while(pos[0]!=i+1):
        if (a[l] <= pos[1]) and (pos[1] <= b[l]):
            pos[1] += 1
            num += 1
        else:
            pos[0] += 1
            num += 1
            l += 1
        if pos[1] == W:
            num = -1
            break
    print(num)

Submission status: Time Limit Exceeded

Solution code:
H, W = (int(x) for x in input().split())
a = []
b = []
for _ in range(min(H, W)):
    _input = input().split()
    a.append(int(_input[0])-1)
    b.append(int(_input[1])-1)
for i in range(H):
    pos = [0, 0]
    num = 0
    l = 0
    while(pos[0]!=i+1):
        if (a[l] <= pos[1]) and (pos[1] <= b[l]):
            pos[1] += 1
            num += 1
        else:
            pos[0] += 1
            num += 1
            l += 1
        if pos[1] == W:
            num = -1
            break
    print(num)

Submission status: Time Limit Exceeded

Solution code:
H, W = (int(x) for x in input().split())
a = []
b = []
for _ in range(min(H, W)):
    _input = input().split()
    a.append(int(_input[0])    )
    b.append(int(_input[1]))
for i in range(H):
    pos = [0, 0]
    num = 0
    l = 0
    while(pos[0]!=i+1):
        if pos[1] == W:
            num = -1
            break
        if (a[l]-1 <= pos[1]) and (pos[1] <= b[l]-1):
            pos[1] += 1
            num += 1
        else:
            pos[0] += 1
            num += 1
            l += 1
    print(num)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
input=sys.stdin.readline

MAX=10**18
h,w=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(h)]
ans=[MAX]*h
for i in range(1,w+1):
    th=0
    tw=i
    start=i
    while tw<=w and th<h:
        if arr[th][0]<=tw<=arr[th][1]:
            tw+=1
        else:
            ans[th]=min(ans[th],th+tw-start+1)
            th+=1
for val in ans:
    if val==MAX:
        print(-1)
    else:
        print(val)

Submission status: Time Limit Exceeded

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####
from collections import defaultdict as ddic, Counter, deque
import heapq, bisect, itertools
MOD = 10 ** 9 + 7

def solve(R, C, A):
    INF = int(1e15) #float('inf')
    dp = range(C)

    ans = []
    for a1, b1 in A:
        #print("yo", a1,b1)
        dp2 = [INF] * C
        if 0 < a1:
            dp2[0] = 1 + dp[0]
        for c in xrange(a1):
            if dp2[c] > dp2[c-1]:
                dp2[c] = dp2[c-1] + 1
            if dp2[c] > dp[c]:
                dp2[c] = dp[c] + 1
        for c in xrange(a1, b1 + 1):
            dp2[c] = dp2[c-1] + 1
        for c in xrange(b1 + 1, C):
            if dp2[c] > dp2[c-1]:
                dp2[c] = dp2[c-1] + 1
            if dp2[c] > dp[c]:
                dp2[c] = dp[c] + 1
        ans.append(min(dp2))
        dp = dp2

    return ans


R, C = rrm()
A = [rrm() for _ in xrange(R)]
for i in xrange(R):
    A[i][0] -= 1
    A[i][1] -= 1

INF = int(1e15)
ans= solve(R, C, A)
for x in ans:
    if x < INF:
        print x
    else:
        print -1

Submission status: Time Limit Exceeded

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####
from collections import defaultdict as ddic, Counter, deque
import heapq, bisect, itertools
MOD = 10 ** 9 + 7

def solve(R, C, A):
    INF = float('inf')
    dp = range(C)

    ans = []
    for a1, b1 in A:
        #print("yo", a1,b1)
        dp2 = [INF] * C
        if 0 < a1:
            dp2[0] = 1 + dp[0]
        for c in xrange(1, C):
            if not(a1 <= c <= b1):
                dp2[c] = min(dp2[c], min(dp2[c-1], dp[c]) + 1)
            else:
                dp2[c] = min(dp2[c], dp2[c-1] + 1)
        ans.append(min(dp2))
        dp = dp2
        #print("!", dp)

    return ans


R, C = rrm()
A = [rrm() for _ in xrange(R)]
for i in xrange(R):
    A[i][0] -= 1
    A[i][1] -= 1

INF = float('inf')
ans= solve(R, C, A)
for x in ans:
    if x < INF:
        print x
    else:
        print -1

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
class Lazysegtree:
    def __init__(self, A, fx, ex, fm, em, fa, initialize = True):
        #fa(operator, idx)の形にしている、data[idx]の長さに依存する場合などのため
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.dep = (self.N-1).bit_length()
        self.fx = fx
        """
        self.fa =
        self.fm = fm
        """

        self.ex = ex
        self.em = em
        self.lazy = [em]*(2*self.N0)
        if initialize:
            self.data = [self.ex]*self.N0 + A + [self.ex]*(self.N0 - self.N)
            for i in range(self.N0-1, -1, -1):
                self.data[i] = self.fx(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [self.ex]*(2*self.N0)

    def fa(self, ope, idx):
        if ope[0]:
            k = idx.bit_length()
            return (idx - (1<<(k-1)))*(1<<(self.dep+1-k)) + ope[1]
        return self.data[idx]
    
    def fm(self, x, y):
        if x[0] == 1:
            return x
        else:
            return y
    
    def __repr__(self):
        s = 'data'
        l = 'lazy'
        cnt = 1
        for i in range(self.N0.bit_length()):
            s = '\n'.join((s, ' '.join(map(str, self.data[cnt:cnt+(1<<i)]))))
            l = '\n'.join((l, ' '.join(map(str, self.lazy[cnt:cnt+(1<<i)]))))
            cnt += 1<<i
        return '\n'.join((s, l))
    
    def _ascend(self, k):
        k = k >> 1
        c = k.bit_length()
        for j in range(c):
            idx = k >> j
            self.data[idx] = self.fx(self.data[2*idx], self.data[2*idx+1])
            
    def _descend(self, k):
        k = k >> 1
        idx = 1
        c = k.bit_length()
        for j in range(1, c+1):
            idx = k >> (c - j)
            if self.lazy[idx] == self.em:
                continue
            self.data[2*idx] = self.fa(self.lazy[idx], 2*idx) 
            self.data[2*idx+1] = self.fa(self.lazy[idx], 2*idx+1)
            self.lazy[2*idx] = self.fm(self.lazy[idx], self.lazy[2*idx])
            self.lazy[2*idx+1] = self.fm(self.lazy[idx], self.lazy[2*idx+1])
            self.lazy[idx] = self.em
            
            
    def query(self, l, r):
        L = l+self.N0
        R = r+self.N0
        self._descend(L//(L & -L))
        self._descend(R//(R & -R)-1)
        
        sl = self.ex
        sr = self.ex                                                                   

        while L < R:
            if R & 1:
                R -= 1
                sr = self.fx(self.data[R], sr)
            if L & 1:
                sl = self.fx(sl, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return self.fx(sl, sr)
    
    def operate(self, l, r, x):
        L = l+self.N0
        R = r+self.N0

        Li = L//(L & -L)
        Ri = R//(R & -R)
        self._descend(Li)
        self._descend(Ri-1)
        
        while L < R :
            if R & 1:
                R -= 1
                self.data[R] = self.fa(x, R)
                self.lazy[R] = self.fm(x, self.lazy[R])
            if L & 1:
                self.data[L] = self.fa(x, L)
                self.lazy[L] = self.fm(x, self.lazy[L])
                L += 1
            L >>= 1
            R >>= 1
        
        self._ascend(Li)
        self._ascend(Ri-1)

INF = 10**18+3

H, W = map(int, readline().split())
T = Lazysegtree([0]*W, min, INF, None, (0, 0), None, initialize = True)
N0 = T.N0
Ans = [None]*H
for qu in range(H):
    a, b = map(int, readline().split())
    a -= 1
    if a == 0:
        T.operate(a, b, (1, INF))
    else:
        x = T.query(a-1, a)
        T.operate(a, b, (1, x-a+1))
    ans = T.query(0, N0) + qu + 1
    if ans >= INF:
        ans = -1
    Ans[qu] = ans 
print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
class LazySegmentTree:

    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = monoid_data * 2
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe] * (self.n * 2)


    def replace(self, index, value):
        index += self.n

        # propagation
        for shift in range(index.bit_length()-1, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # update
        self.data[index] = value
        self.lazy[index] = self.oe

        # recalculation
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def effect(self, l, r, operator):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # effect
        while l < r:
            if l % 2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r % 2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        # recalculation
        i = l0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
        i = r0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
            
        
    def folded(self, l, r):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # fold
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l % 2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
def fmo(m1, o1):
    if o1 == -1:
        return m1
    return o1
def foo(o1, o2):
    if o2 == -1:
        return o1
    return o2
INF = 10**6
lst_max = LazySegmentTree(list(range(w)), -INF, -1, max, fmo, foo)
lst_min = LazySegmentTree([0]*w, INF, -1, min, fmo, foo)
for i in range(h):
    a, b = map(int, input().split())
    a -= 1
    l_max = lst_max.folded(a, b)
    lst_max.effect(a, b, -INF)
    lst_min.effect(a, b, INF)
    if b < w:
        x = lst_max.folded(b, b+1)
        lst_max.replace(b, max(l_max, x))
        y = lst_min.folded(b, b+1)
        lst_min.replace(b, min(b-l_max, y))
    ans = lst_min.folded(0, w)
    if ans == INF:
        print(-1)
    else:
        ans += i+1
        print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

class SegTreeFlag():
    def segFunc(self, x, y):
        return x+y
    def searchIndexFunc(self, val):
        return val > 0
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segFunc(self.seg[2*i+1],self.seg[2*i+2])
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res
    def getLargestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R)//2
            if self.searchIndexFunc(self.query(P, R)):
                L = P
            else:
                R = P
        return L
    def getSmallestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R+1)//2
            if self.searchIndexFunc(self.query(L, P)):
                R = P
            else:
                L = P
        return L

class SegTreeMin():
    def segFunc(self, x, y):
        if x < y:
            return x
        else:
            return y
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segFunc(self.seg[2*i+1],self.seg[2*i+2])
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res

h, w = map(int, input().split())
wall = [list(map(int, input().split())) for _ in range(h)]
ans = [-1 for _ in range(h)]
segflag = SegTreeFlag(0, [1 for _ in range(w+2)])
segmin = SegTreeMin(10**9, [0 for _ in range(w+2)])
segmin.update(0, 10**9)
for i in range(h):
    idx = segflag.getLargestIndex(0, wall[i][1]+2)
    if idx < wall[i][1]+1:
        segflag.update(wall[i][1]+1, 1)
        segmin.update(wall[i][1]+1, segmin.query(idx, idx+1)+(wall[i][1]+1-idx))
    cnt = segflag.query(wall[i][0], wall[i][1]+1)
    for _ in range(cnt):
        idx = segflag.getSmallestIndex(wall[i][0], wall[i][1]+1)
        segflag.update(idx, 0)
        segmin.update(idx, 10**9)
    tmp = segmin.query(0, w+1)
    if tmp < 10**9:
        ans[i] = tmp + i + 1
    else:
        break
for v in ans:
    print(v)

Submission status: Accepted

Solution code:
import numpy as np
i4 = np.int32
i8 = np.int64


def solve(a, b, H, W):
    ret = np.empty(H, i8)
    for i in range(H):
        ret[i] = -1
    dp0 = np.arange(W)
    dp = np.arange(W)
    arg0 = W - 1
    arg = 0
    for i in range(H):
        r1 = np.searchsorted(dp, a[i])
        r2 = np.searchsorted(dp, b[i])
        if b[i] == W:
            if r1 == 0:
                return ret
            else:
                dp0 = dp0[: r1]
                dp = dp[: r1]
        else:
            dp[r1:r2] = b[i]

        if arg0 > -1:
            if r1 <= arg0 < r2:
                for j in range(r1 - 1, -1, -1):
                    if dp[j] == dp0[j]:
                        arg0 = j
                        ret[i] = i + 1
                        break
                else:
                    arg0 = -1
                    arg = np.argmin(dp - dp0)
                    ret[i] = dp[arg] - dp0[arg] + i + 1
            else:
                ret[i] = i + 1
        else:
            if r1 <= arg < r2:
                arg = np.argmin(dp - dp0)
            ret[i] = dp[arg] - dp0[arg] + i + 1

        if i % 1000 == 999:
            m = 0
            prev = dp[0]
            for k in range(1, dp.shape[0]):
                if dp[k] > prev:
                    dp0[m] = dp0[k - 1]
                    dp[m] = prev
                    m += 1
                    prev = dp[k]
            else:
                dp0[m] = dp0[dp0.shape[0] - 1]
                dp[m] = prev
                m += 1
            dp0 = dp0[: m]
            dp = dp[: m]
            if arg0 > -1:
                for j in range(m - 1, -1, -1):
                    if dp[j] == dp0[j]:
                        arg0 = j
                        break
            else:
                arg = np.argmin(dp - dp0)
    return ret


def main(in_file):
    stdin = open(in_file)
    H, W = [int(x) for x in stdin.readline().split()]
    ab = np.fromstring(stdin.read(), i8, sep=' ').reshape((-1, 2)).T.copy()
    ans = solve(ab[0] - 1, ab[1], H, W)
    p = '\n'.join([str(x) for x in ans.tolist()])
    print(p)


def cc_export():
    from numba.pycc import CC
    from numba.types import Array, int64
    cc = CC('my_module')
    cc.export('solve', (Array(int64, 1, 'C'), Array(int64, 1, 'C'), int64, int64))(solve)
    cc.compile()


if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main('/dev/stdin')

Submission status: Accepted

Solution code:
from heapq import *
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class BitSum:
    def __init__(self, n):
        self.n = n + 1
        self.table = [0] * self.n

    def add(self, i, x):
        i += 1
        while i < self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

    # 数列を度数分布とみたときに、x番目がどのインデックスにあるかを返す
    def rank(self, x):
        idx = 0
        for lv in range((self.n - 1).bit_length() - 1, -1, -1):
            mid = idx + (1 << lv)
            if mid >= self.n: continue
            if self.table[mid] < x:
                x -= self.table[mid]
                idx += 1 << lv
        return idx

def solve():
    bit = BitSum(w + 1)
    for j in range(w): bit.add(j + 1, 1)
    cost = [0] * (w + 1)
    hp = [0] * w
    heapify(hp)
    rem = []

    for i in range(h):
        l, r = MI()
        r += 1
        # cost[r]の更新
        if r <= w:
            cnt = bit.sum(r)
            if cnt:
                j = bit.rank(cnt)
                if l <= j < r:
                    bit.add(r, 1)
                    cost[r] = cost[j] + r - j
                    heappush(hp, cost[r])
        # 区間[l,r)を無効にする
        cnt = bit.sum(l - 1)
        while 1:
            j = bit.rank(cnt + 1)
            if j >= r: break
            heappush(rem, cost[j])
            bit.add(j, -1)
        # ヒープからの削除
        while hp and rem and hp[0] == rem[0]:
            heappop(hp)
            heappop(rem)
        # 出力
        if hp: print(hp[0] + i + 1)
        else: print(-1)

h,w=MI()
solve()

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class BitSum:
    def __init__(self, n):
        self.n = n + 1
        self.table = [0] * self.n

    def add(self, i, x):
        i += 1
        while i < self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

    # 数列を度数分布とみたときに、x番目がどのインデックスにあるかを返す
    def rank(self, x):
        idx = 0
        for lv in range((self.n - 1).bit_length() - 1, -1, -1):
            mid = idx + (1 << lv)
            if mid >= self.n: continue
            if self.table[mid] < x:
                x -= self.table[mid]
                idx += 1 << lv
        return idx

def solve():
    bit = BitSum(w + 1)
    for j in range(w): bit.add(j + 1, 1)
    cost = [0] * (w + 1)
    hp = [0] * w
    heapify(hp)
    rem = []

    for i in range(h):
        l, r = MI()
        r += 1
        # cost[r]の更新
        if r <= w:
            cnt = bit.sum(r)
            if cnt:
                j = bit.rank(cnt)
                if l <= j < r:
                    bit.add(r, 1)
                    cost[r] = cost[j] + r - j
                    heappush(hp, cost[r])
        # 区間[l,r)を無効にする
        cnt = bit.sum(l - 1)
        while 1:
            j = bit.rank(cnt + 1)
            if j >= r: break
            heappush(rem, cost[j])
            bit.add(j, -1)
        # ヒープからの削除
        while hp and rem and hp[0] == rem[0]:
            heappop(hp)
            heappop(rem)
        # 出力
        if hp: print(hp[0] + i + 1)
        else: print(-1)

h,w=MI()
solve()

Submission status: Accepted

Solution code:
# 写経
# https://atcoder.jp/contests/abc177/submissions/16463802

import numpy as np
i4 = np.int32
i8 = np.int64
  
def solve(a, b, H, W):
    ret = np.empty(H, i8)
    for i in range(H):
        ret[i] = -1
    dp0 = np.arange(W) #初期位置
    dp = np.arange(W) #現在位置
    arg0 = W - 1
    arg = 0
    for i in range(H):
        r1 = np.searchsorted(dp, a[i])
        r2 = np.searchsorted(dp, b[i])
        if b[i] == W: #右端まで壁が続く場合
            if r1 == 0:
                return ret
            else:
                dp0 = dp0[: r1] #壁があるところより先は無視する
                dp = dp[: r1]
        else:
            dp[r1:r2] = b[i] #合流させる
 
        if arg0 > -1:   #直進する流れが残っている場合
            if r1 <= arg0 < r2: #壁がある場合
                for j in range(r1 - 1, -1, -1):
                    if dp[j] == dp0[j]: 
                        arg0 = j    #ここまで直進してきた他の流れに乗り換える
                        ret[i] = i + 1
                        break
                else:
                    arg0 = -1
                    arg = np.argmin(dp - dp0) #残っている値の中での最小値
                    ret[i] = dp[arg] - dp0[arg] + i + 1
            else:
                ret[i] = i + 1
        else: 
            if r1 <= arg < r2:
                arg = np.argmin(dp - dp0)
            ret[i] = dp[arg] - dp0[arg] + i + 1
        
        
        if i % 1000 == 999:
            m = 0
            prev = dp[0]
            for k in range(1, dp.shape[0]):
                if dp[k] > prev: #dp[0]とは別の流れにあるものについて
                    dp0[m] = dp0[k - 1] #最小のずれを持つもののみ残してまとめる
                    dp[m] = prev 
                    m += 1
                    prev = dp[k]
            else: #流れが一つのみの場合はこの流れの実を追いかける
                dp0[m] = dp0[dp0.shape[0] - 1]
                dp[m] = prev
                m += 1
            dp0 = dp0[: m]
            dp = dp[: m]
            if arg0 > -1: #現在最小である流れなどの情報も更新しておく
                for j in range(m - 1, -1, -1):
                    if dp[j] == dp0[j]:
                        arg0 = j
                        break
            else:
                arg = np.argmin(dp - dp0)
        
    return ret
 
 
def main(in_file):
    stdin = open(in_file)
    H, W = [int(x) for x in stdin.readline().split()]
    ab = np.fromstring(stdin.read(), i8, sep=' ').reshape((-1, 2)).T.copy()
    ans = solve(ab[0] - 1, ab[1], H, W)
    p = '\n'.join([str(x) for x in ans.tolist()])
    print(p)
 
 
def cc_export():
    from numba.pycc import CC
    from numba.types import Array, int64
    cc = CC('my_module')
    cc.export('solve', (Array(int64, 1, 'C'), Array(int64, 1, 'C'), int64, int64))(solve)
    cc.compile()
 
 
if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main('/dev/stdin')