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:
import sys
input = lambda: sys.stdin.readline().rstrip()

class SegmentTreeDual():
    def __init__(self, init, unitX, unitA, g, h):
        self.g = g # (X, A, size) -> X
        self.h = h # (A, A) -> A
        self.unitA = unitA
        if type(init) == int:
            self.n = init
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
    
    def debug(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")
class SegmentTree():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f # (X, X) -> X
        self.g = g # (X, A, size) -> X
        self.h = h # (A, A) -> A
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def update(self, i, x):
        i += self.n
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
            i >>= 1
    
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def calc_above(self, i):
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2|1))
            i >>= 1
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getrange(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        
        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
        
        self.calc_above(l0)
        self.calc_above(r0)
    
    def debug(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")

H, W = map(int, input().split())
inf = 1 << 18
g = lambda x, a, s: x if a == -1 else a
h = lambda a, b: a if b == -1 else b
unitA = -1
unitX = inf
N = W + 2
st1 = SegmentTreeDual([-inf] + [i for i in range(1, W + 1)] + [-inf] * (N - W - 1), unitX, unitA, g, h)

f2 = lambda x, y: min(x, y)
g2 = lambda x, a, s: x if a == -1 else a
h2 = lambda a, b: a if b == -1 else b
unitX = inf
unitA = -1
st2 = SegmentTree([inf] + [0 for i in range(1, W + 1)] + [inf] * (N - W - 1), unitX, unitA, f2, g2, h2)
for i in range(H):
    a, b = map(int, input().split())
    b += 1
    l = st1.getvalue(a-1)
    st2.operate_range(a, a+1, a - l)
    st2.operate_range(a+1, b, inf)
    r = st1.getvalue(b)
    st2.operate_range(b, b+1, b - r)
    st1.operate_range(a, b, l)
    t = st2.getrange(0, N)
    print(t + i + 1 if t < inf else -1)

Submission status: Time Limit Exceeded

Solution code:

"""

縦の移動回数は無視できない
戻る必要があるのは1段まで？
普通の縦の移動は省く→余計に増える分だけカウント

dp[i][j] = i行目で、j番目のセルに移動する最小コスト
→区間更新が必要…
基本的に上から引き継ぎ

最短距離は列内では1づつ増えるはずなのを利用して高速計算
→一番距離が短い場所(禁止区間の左右で)と、その距離を保持してdpする

自分の左端を保持→左端はスコアを保持すればいい？
縦を除いた自分の最短距離 + W-jを保存することにする
最初は、W,W-1,W-2…,1
更新時は、左端の値で区間を全部塗りつぶせばいい


"""

#遅延評価セグメント木(tree&lazy)を作る。初期値lisを渡す
#defaultで初期化する
 
def make_LST(lis,default = float("inf")):
 
    n = 1
    while n < len(lis):
        n *= 2
 
    tree = [default] * (2*n-1)
    lazy = [None] * (2*n-1)
 
    for i in range(len(lis)):
        tree[i+n-1] = lis[i]
    for i in range(n-2,-1,-1):
        tree[i] = min(tree[i*2+1] , tree[i*2+2])
 
    return tree,lazy
 
def eval_LST(k,l,r,tree,lazy):
    if lazy[k] != None:
        #print (k,lazy[k],l)
        tree[k] = lazy[k][0] + l-lazy[k][1]
 
    if r-l > 1:
        eval_LST(2*k+1,l,(l+r)//2,tree,lazy)
        lazy[2*k+1] = lazy[k]
        eval_LST(2*k+2,(l+r)//2,r,tree,lazy)
        lazy[2*k+2] = lazy[k]
 
    lazy[k] = None
 
#add x to [a,b)
def change_LST(a,b,x,s,tree,lazy,k=0,l=0,r=-1):
 
    if r < 0:
        n = (len(tree)+1)//2
        r = n
 
    eval_LST(k,l,r,tree,lazy)
 
    if b <= l or r <= a:
        return
 
    if a <= l and r <= b:
        eval_LST(k,l,r,tree,lazy)
        lazy[k] = (x,s)
        eval_LST(k,l,r,tree,lazy)
    else:
        change_LST(a,b,x,s,tree,lazy,2*k+1,l,(l+r)//2)
        change_LST(a,b,x,s,tree,lazy,2*k+2,(l+r)//2,r)
        tree[k] = min(tree[2*k+1] , tree[2*k+2])
 
#range_minimum_query(def)
def rmq_LST(a,b,tree,lazy,k=0,l=0,r=-1):
    if r < 0:
        n = (len(tree)+1)//2
        r = n
    if b <= l or r <= a:
        return float("inf")
 
    eval_LST(k,l,r,tree,lazy)
    if a <= l and r <= b:
        return tree[k]
 
    vl = rmq_LST(a,b,tree,lazy,2*k+1,l,(l+r)//2)
    vr = rmq_LST(a,b,tree,lazy,2*k+2,(l+r)//2,r)
 
    return min(vl,vr)
 
def getfrom_index_LST(index,tree,lazy):
    return rmq_LST(index,index+1,tree,lazy)
 
def upd_point_LST(index,newnum,tree,lazy):
    oldnum = getfrom_index_LST(index,tree,lazy)
    difference = newnum - oldnum
    add_LST(index,index+1,difference,tree,lazy)


from sys import stdin
H,W = map(int,stdin.readline().split())

lis = [0] * W
tree,lazy = make_LST(lis,default = float("inf"))

for i in range(H):
    a,b = map(int,stdin.readline().split())
    a -= 1
    b -= 1

    if a != 0:
        x = getfrom_index_LST(a-1,tree,lazy)
        change_LST(a,b+1,x,a-1,tree,lazy)
    else:
        change_LST(a,b+1,float("inf"),a,tree,lazy)

    #print (tree,lazy)
    ans = (1+i+ rmq_LST(0,W,tree,lazy))
    if ans == float("inf"):
        print (-1)
    else:
        print (ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
ran=[[j-1 for j in list(map(int,input().split()))] for i in range(h)]
cand=[]
if ran[0][0]>1:
    cand.append(0)
    cand.append(ran[0][0]-1)
elif ran[0][0]==1:
    cand.append(ran[0][0]-1)
if ran[0][1]<w-2:
    cand.append(w-1)
    cand.append(ran[0][1]+1)
elif ran[0][1]==w-2:
    cand.append(ran[0][1]+1)
cand=list(range(w))
dp=[[[-1,-1] for j in range(h+1)] for i in range(len(cand))]
ans=[-1]*h
for i in range(len(cand)):
    dp[i][0]=[cand[i],0]
    for j in range(h):
        if dp[i][j][0]<ran[j][0]:
            if ran[j][0]==0:
                break
            else:
                dp[i][j+1]=[dp[i][j][0],dp[i][j][1]+1]
        elif dp[i][j][0]<=ran[j][1]:
            if ran[j][1]==w-1:
                break
            else:
                dp[i][j+1]=[ran[j][1]+1,dp[i][j][1]+(ran[j][1]-dp[i][j][0]+1)+1]
        else:
            dp[i][j+1]=[dp[i][j][0],dp[i][j][1]+1]
    for j in range(h):
        if dp[i][j+1][1]!=-1:
            if ans[j]!=-1:
                ans[j]=min(ans[j],dp[i][j+1][1])
            else:
                ans[j]=dp[i][j+1][1]
for i in range(h):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()


class SegmentTree1():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f # (X, X) -> X
        self.g = g # (X, A, size) -> X
        self.h = h # (A, A) -> A
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
            # for i in range(self.n-1, 0, -1):
            #     self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def update(self, i, x):
        return
        i += self.n
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
            i >>= 1
    
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def calc_above(self, i):
        return
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2|1))
            i >>= 1
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getrange(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        
        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
        
        self.calc_above(l0)
        self.calc_above(r0)
    
    def debug(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")
class SegmentTree():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f # (X, X) -> X
        self.g = g # (X, A, size) -> X
        self.h = h # (A, A) -> A
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def update(self, i, x):
        i += self.n
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
            i >>= 1
    
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def calc_above(self, i):
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2|1))
            i >>= 1
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getrange(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        
        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
        
        self.calc_above(l0)
        self.calc_above(r0)
    
    def debug(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")

H, W = map(int, input().split())
inf = 1 << 18
f = lambda x, y: x
g = lambda x, a, s: x if a == -1 else a
h = lambda a, b: a if b == -1 else b
N = W + 2
st1 = SegmentTree1([-inf] + [i for i in range(1, W + 1)] + [-inf] * (N - W - 1) , 0, -1, f, g, h)
f2 = lambda x, y: min(x, y)
g2 = lambda x, a, s: x if a == -1 else a
h2 = lambda a, b: a if b == -1 else b
st2 = SegmentTree([inf] + [0 for i in range(1, W + 1)] + [inf] * (N - W - 1), inf, -1, f2, g2, h2)
for i in range(H):
    a, b = map(int, input().split())
    b += 1
    l = st1.getvalue(a-1)
    st2.operate_range(a, a+1, a - l)
    st2.operate_range(a+1, b, inf)
    r = st1.getvalue(b)
    st2.operate_range(b, b+1, b - r)
    st1.operate_range(a, b, l)
    t = st2.getrange(0, N)
    print(t + i + 1 if t < inf else -1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

H, W, *AB = map(int, read().split())
AB_list = [(-1,-1)]
for i in range(H):
    a, b = AB[2*i], AB[2*i+1]
    AB_list.append((a,b))

min_list = [INF] * (H+3)
MAP = [[INF] * (W + 2) for _ in range(H + 3)]

def bfs(start):
    queue = deque([(start + (0,))])
    while queue:
        ci,cj, count = queue.popleft()
        if min_list[ci] > count:
            min_list[ci] = count

        if ci == H+1:break
        a, b = AB_list[ci]

        if a <= cj <= b:
            if b + 1 <= W:
                queue.append((ci+1, b + 1, count + b- cj + 2))

        elif ci + 1 <= H+1:
            queue.append((ci+1, cj, count + 1))


def run():
    a1, b1 = AB_list[1]
    for j in range(1, W+1):
        if a1 <= j <= b1:continue
        bfs((1, j))

    for v in min_list[2:-1]:
        if v == INF:
            print(-1)
        else:
            print(v)

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

H, W, *AB = map(int, read().split())
AB_list = [(-1,-1)]
for i in range(H):
    a, b = AB[2*i], AB[2*i+1]
    AB_list.append((a,b))

min_list = [INF] * (H+3)
MAP = [[INF] * (W + 2) for _ in range(H + 3)]

def bfs(start):
    queue = deque([(start + (0,))])
    while queue:
        ci,cj, count = queue.popleft()
        if min_list[ci] > count:
            min_list[ci] = count

        if ci == H+1:continue
        a, b = AB_list[ci]

        if a <= cj <= b:
            if b + 1 <= W:
                queue.append((ci+1, b + 1, count + b- cj + 2))

        elif ci + 1 <= H+1:
            queue.append((ci+1, cj, count + 1))


def run():
    a1, b1 = AB_list[1]
    for j in range(1, W+1):
        if a1 <= j <= b1:continue
        bfs((1, j))

    for v in min_list[2:-1]:
        if v == INF:
            print(-1)
        else:
            print(v)

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

H, W, *AB = map(int, read().split())
AB_list = [(-1,-1)]
for i in range(H):
    a, b = AB[2*i], AB[2*i+1]
    AB_list.append((a,b))

min_list = [INF] * (H+3)
MAP = [[INF] * (W + 2) for _ in range(H + 3)]

def bfs(start):
    queue = deque([(start + (0,))])
    while queue:
        ci,cj, count = queue.popleft()
        if min_list[ci] > count:
            min_list[ci] = count

        if ci == H+1:continue
        a, b = AB_list[ci]

        if a <= cj <= b:
            if b + 1 <= W:
                queue.append((ci+1, b + 1, count + b- cj + 2))

        elif ci + 1 <= H+1:
            queue.append((ci+1, cj, count + 1))


def run():
    for j in range(1, W+1):
        bfs((1, j))

    for v in min_list[2:-1]:
        if v == INF:
            print(-1)
        else:
            print(v)

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
Y, X = map(int, input().split())
Wall = []
for i in range(Y):
    a, b = map(int, input().split())
    Wall.append((a,b))


inf = 10**11

from collections import deque
def bfs():
    ans = [inf]*(Y+1)
    dist = list([inf]*X for _ in range(Y+1))
    queue = deque()
    a, b = Wall[0]
    for i in range(X):
        if i < a-1 or b-1 < i:
            dist[0][i] = 0
            queue.append((0,i))
    while queue:
        y, x = queue.popleft()
        ans[y] = min(ans[y], dist[y][x])
        u, t = y, x+1
        if t < X:
            if dist[u][t] > dist[y][x] + 1:
                dist[u][t] = dist[y][x] + 1
                queue.append((u, t))
        u, t = y+1, x
        if u < Y+1:
            a, b = Wall[y]
            if a-1 <= x and x <= b-1:
                continue
            if dist[u][t] > dist[y][x] + 1:
                dist[u][t] = dist[y][x] + 1
                queue.append((u, t))
    return ans
    
ans = bfs()
for i in range(1,Y+1):
    if ans[i] < inf:
        print(ans[i])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

H, W, *AB = map(int, read().split())
AB_list = [(-1,-1)]
for i in range(H):
    a, b = AB[2*i], AB[2*i+1]
    AB_list.append((a,b))

min_list = [INF] * (H+3)
MAP = [[INF] * (W + 2) for _ in range(H + 3)]

def bfs(start):
    queue = deque([(start + (0,))])
    while queue:
        ci,cj, count = queue.popleft()
        min_list[ci] = min(min_list[ci], count)
        if ci == H+1:continue
        a, b = AB_list[ci]

        if a <= cj <= b:
            if b + 1 <= W:
                queue.append((ci, b + 1, count + b- cj + 1))

        elif ci + 1 <= H+1:
            queue.append((ci+1, cj, count + 1))


def run():
    for j in range(1, W+1):
        bfs((1, j))

    for v in min_list[2:-1]:
        if v == INF:
            print(-1)
        else:
            print(v)

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

H, W, *AB = map(int, read().split())
AB_list = [(-1,-1)]
for i in range(H):
    a, b = AB[2*i], AB[2*i+1]
    AB_list.append((a,b))

min_list = [INF] * (H+3)
MAP = [[INF] * (W + 2) for _ in range(H + 3)]

def bfs(start):
    queue = deque([(start + (0,))])
    while queue:
        ci,cj, count = queue.popleft()
        if MAP[ci][cj] > count:
            MAP[ci][cj] = count
            min_list[ci] = min(min_list[ci], count)
        else:
            continue
        if ci == H+1:continue
        a, b = AB_list[ci]

        if a <= cj <= b:
            if b + 1 <= W:
                queue.append((ci, b + 1, count+ b- cj + 1))

        elif ci + 1 <= H+1:
            queue.append((ci+1, cj, count + 1))


def run():
    for j in range(1, W+1):
        bfs((1, j))

    for v in min_list[2:-1]:
        if v == INF:
            print(-1)
        else:
            print(v)

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def Binary_Search(lSeg, B):
	#初期化
	left = 0; right = B
	ind = 0
	
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		if lSeg.query(mid, B) != INF:
			ind = max(ind, mid)
			left = mid + 1
		else:
			right = mid - 1

	return ind

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	# 区間クエリの種類
	def calc(self, a, b):
		return min(a, b)

	# 遅延伝播を行うindexを生成
	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	# 遅延伝搬処理
	def propagates(self, *ids):
		for i in reversed(ids):
			v = self.lazy[i - 1]
			if not v:
				continue
			self.lazy[2 * i - 1] += v; self.lazy[2 * i] += v
			self.data[2 * i - 1] += v; self.data[2 * i] += v
			self.lazy[i - 1] = 0

	# 区間[l, r]にxを加算
	def update(self, l, r, x):
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		while L < R:
			if R & 1:
				R -= 1
				self.lazy[R - 1] += x; self.data[R - 1] += x
			if L & 1:
				self.lazy[L - 1] += x; self.data[L - 1] += x
				L += 1
			L >>= 1; R >>= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

	def update2(self, l, r, x):
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		while L < R:
			if R & 1:
				R -= 1
				self.lazy[R - 1] = x; self.data[R - 1] = x
			if L & 1:
				self.lazy[L - 1] = x; self.data[L - 1] = x
				L += 1
			L >>= 1; R >>= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])


	# 区間[l, r]内の最小値を求める
	def query(self, l, r):
		self.propagates(*self.gindex(l, r + 1))
		L = self.N0 + l; R = self.N0 + r + 1

		s = INF
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
		return s

#処理内容
def main():
	H, W = getlist()
	lSeg = lazySegTree(W)
	for i in range(H):
		A, B = getlist()
		A -= 1; B -= 1
		val = INF
		if B != W - 1:
			ind = Binary_Search(lSeg, B + 1)
			val = lSeg.query(ind, ind) + (B + 1 - ind)

		# 左側加算
		# if A >= 1:
		# 	lSeg.update(0, A - 1, 1)
		# 壁処理
		lSeg.update(A, B, INF)
		# 右側加算
		# if B < W - 1:
		# 	lSeg.update(B + 1, W - 1, 1)

		if val != INF:
			if lSeg.query(B + 1, B + 1) > val:
				lSeg.update2(B + 1, B + 1, val)

		ans = lSeg.query(0, W - 1) + 1 + i
		# print(lSeg.data[3:])
		if ans == INF:
			print(-1)
		else:
			print(ans)


if __name__ == '__main__':
	main()