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
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

H,W=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(H)]

# 範囲更新、最大値取得の遅延セグ木と、範囲更新、最小値取得の遅延セグ木

seg_el=1<<((W+3).bit_length()) # Segment treeの台の要素数
SEG=[1<<30]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

SEG2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def indexes(L,R):
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def updates(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
    
    while L!=R:
        if L > R:
            SEG[L]=x
            LAZY[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=x
            LAZY[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=max(SEG[ind<<1],SEG[1+(ind<<1)])

def updates2(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
    
    while L!=R:
        if L > R:
            SEG2[L]=x
            LAZY2[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG2[R]=x
            LAZY2[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG2[ind]=min(SEG2[ind<<1],SEG2[1+(ind<<1)]) 
        
def getvalues(l,r): # 区間[l,r)に関するmaxを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
            
    ANS=-1<<30

    while L!=R:
        if L > R:
            ANS=max(ANS , SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=max(ANS , SEG[R])
            R//=(R & (-R))

    return ANS

def getvalues2(l,r): # 区間[l,r)に関するminを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
            
    ANS=1<<31

    while L!=R:
        if L > R:
            ANS=min(ANS , SEG2[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=min(ANS , SEG2[R])
            R//=(R & (-R))

    return ANS

for i in range(W+1):
    updates(i,i+1,i)

for i in range(H):
    x,y = D[i]
    if x==1:
        updates(x,y+1,-(1<<30))
    else:
        MAX=getvalues(1,x)
        updates(x,y+1,MAX)

    updates2(x,y+1,1<<30)
    updates2(y+1,y+2,y+1-getvalues(y+1,y+2))

    ANS=getvalues2(1,W+1)+i+1
    if ANS>1<<28:
        sys.stdout.write(str(-1)+"\n")
    else:
        sys.stdout.write(str(ANS)+"\n")

Submission status: Time Limit Exceeded

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

H,W=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(H)]

# 範囲更新、最大値取得の遅延セグ木と、範囲更新、最小値取得の遅延セグ木

seg_el=1<<((W+3).bit_length()) # Segment treeの台の要素数
SEG=[1<<30]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

SEG2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def indexes(L,R):
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def updates(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
    
    while L!=R:
        if L > R:
            SEG[L]=x
            LAZY[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=x
            LAZY[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=max(SEG[ind<<1],SEG[1+(ind<<1)])

def updates2(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
    
    while L!=R:
        if L > R:
            SEG2[L]=x
            LAZY2[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG2[R]=x
            LAZY2[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG2[ind]=min(SEG2[ind<<1],SEG2[1+(ind<<1)]) 
        
def getvalues(l,r): # 区間[l,r)に関するmaxを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
            
    ANS=-1<<30

    while L!=R:
        if L > R:
            ANS=max(ANS , SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=max(ANS , SEG[R])
            R//=(R & (-R))

    return ANS

def getvalues2(l,r): # 区間[l,r)に関するminを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
            
    ANS=1<<31

    while L!=R:
        if L > R:
            ANS=min(ANS , SEG2[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=min(ANS , SEG2[R])
            R//=(R & (-R))

    return ANS

for i in range(W+1):
    updates(i,i+1,i)

for i in range(H):
    x,y = D[i]
    if x==1:
        updates(x,y+1,-(1<<30))
    else:
        MAX=getvalues(1,x)
        updates(x,y+1,MAX)

    updates2(x,y+1,1<<30)
    updates2(y+1,y+2,y+1-getvalues(y+1,y+2))

    ANS=getvalues2(1,W+1)+i+1
    if ANS>1<<28:
        print(-1)
    else:
        print(ANS)

Submission status: Time Limit Exceeded

Solution code:
H, W= map(int, input().split())

X=[[0 for i in range (W)] for i in range (H+1)]
for i in range(H):
    a,b=map(int, input().split())
    for j in range(a-1,b):
        X[i][j]+=1


Y=[[0 for i in range (W)] for i in range (H+1)]

for i in range(0,H):
    for j in range(W):
        if Y[i][j]==-1:
            Y[i+1][j]=-1
        elif X[i][j]==0:
            Y[i+1][j]=Y[i][j]+1
        elif j==0:
            Y[i+1][j]=-1
        elif Y[i+1][j-1]==-1:
            Y[i+1][j]=-1
        else:
            Y[i+1][j]=Y[i+1][j-1]+1
            
for i in range(1,len(Y)):
    if Y[i][-1]==-1:
        print(-1)
    else:
        Y[i].sort()
        a=0
        while True:
            if Y[i][a] !=-1:
                print(Y[i][a])
                break
            a+=1

Submission status: Time Limit Exceeded

Solution code:
def dfs(st,n,i,x,y):
    global ans
    if x==h or myMap[x][y]=='#':
        return
    else:
        if myMap[x+1][y]=='@':
            dfs(st,n+1,i,x,y+1)
        else:
            ans[i][st]=n+1
            dfs(st,n+1,i+1,x+1,y)

h,w = map(int,input().split())
ans = [[(5 * 10**5) for j in range(w)] for i in range(h)]
myMap = []
myMap.append(['S' for j in range(w)]+['#'])
myMap += [['.' for j in range(w)] + ['#'] for i in range(h+1)]

for i in range(h):
    a,b = map(int,input().split())
    for j in range(a,b+1):
        myMap[i+1][j-1] = '@'
#print(h,w)
#for i in range(len(myMap)):
#    print(myMap[i])

for j in range(w):
    dfs(j,0,0,0,j)

for i in range(h):
    tmp = min(ans[i])
    if tmp == 5 * 10**5:
        print(-1)
    else:
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/abc177/tasks/abc177_f

普通の遅延セグ木で殴れないか？を考える
ある点から連続して大きくなっている場合
どこから大きくなっているかを保持する必要がある
左端を管理するセグ木を用意する(区間更新,一転取得？)
実際の最小値は、左端しかなる可能性がない
→A-1番目とB+1番目を左端情報から更新し、内側をinfで埋めればいい

ほんとか？
→最小値のところだけちゃんと保存されていればいい

x12345x
   ------

情報が不足することはない？


そこに到達できる最大のy座標をもっておく
その時、更新はa-1番目のやつで置き換えるだけ
新たに最小値となりうるのは左端&右端だけなので
1本目のセグ木の情報から、最短経路を置き換える

"""

class LazySegTree:

    def __init__(self,N,first):
        
        self.LV = (N-1).bit_length() 
        self.NO = 2**self.LV
        self.First = first
        self.data = [first] * (2*self.NO)
        self.lazy = [None] * (2*self.NO)

    def calc(self,l,r):
        return min(l,r)

    def gindex(self,l,r):

        L = l + self.NO
        R = r + self.NO

        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1

        while L:
            yield L
            L >>= 1

    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None

    def update(self , l, r, x):
        *ids, = self.gindex(l, r)
        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*ids)
     
        # 2. 区間[l, r)のdata, lazyの値を更新
        L = self.NO + l; R = self.NO + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1; R >>= 1

        # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
        for i in ids:
            self.data[i-1] = self.calc(self.data[2*i-1], self.data[2*i])

    def query(self , l, r):
        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.NO + l; R = self.NO + r

        # 2. 区間[l, r)の最小値を求める
        s = self.First
        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

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

LT = LazySegTree(W,float("inf")) #左端保存
ST = LazySegTree(W,float("inf")) #最小値保存

ST.update(0,W,0)
for i in range(W):
    LT.update(i,i+1,i)

for i in range(H):

    a,b = map(int,stdin.readline().split())
    a -= 1
    b -= 1
    
    if a-1 >= 0:
        new = LT.query(a-1,a)
        ST.update(a-1,a,a-1-new)
    else:
        new = float("-inf")
    LT.update(a,b+1,new)
    ST.update(a,b+1,float("inf"))

    if b+1 < W:
        nind = LT.query(b+1,b+2)
        ST.update(b+1,b+2,b+1-nind)

    ans = (ST.query(0,W)+i+1)
    if ans == float("inf"):
        print (-1)
    else:
        print (ans)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/abc177/tasks/abc177_f

普通の遅延セグ木で殴れないか？を考える
ある点から連続して大きくなっている場合
どこから大きくなっているかを保持する必要がある
左端を管理するセグ木を用意する(区間更新,一転取得？)
実際の最小値は、左端しかなる可能性がない
→A-1番目とB+1番目を左端情報から更新し、内側をinfで埋めればいい

ほんとか？
→最小値のところだけちゃんと保存されていればいい

x12345x
   ------

情報が不足することはない？


そこに到達できる最大のy座標をもっておく
その時、更新はa-1番目のやつで置き換えるだけ
新たに最小値となりうるのは左端&右端だけなので
1本目のセグ木の情報から、最短経路を置き換える

"""

class LazySegTree:

    def __init__(self,N,first):
        
        self.LV = (N-1).bit_length() 
        self.NO = 2**self.LV
        self.First = first
        self.data = [first] * (2*self.NO)
        self.lazy = [None] * (2*self.NO)

    def calc(self,l,r):
        return min(l,r)

    def gindex(self,l,r):

        L = l + self.NO
        R = r + self.NO

        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1

        while L:
            yield L
            L >>= 1

    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None

    def update(self , l, r, x):
        *ids, = self.gindex(l, r)
        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*ids)
     
        # 2. 区間[l, r)のdata, lazyの値を更新
        L = self.NO + l; R = self.NO + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1; R >>= 1

        # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
        for i in ids:
            self.data[i-1] = self.calc(self.data[2*i-1], self.data[2*i])

    def query(self , l, r):
        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.NO + l; R = self.NO + r

        # 2. 区間[l, r)の最小値を求める
        s = self.First
        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

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

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


LT = LazySegTree(W,float("inf")) #左端保存
ST = LazySegTree(W,float("inf")) #最小値保存

ST.update(0,W,0)
for i in range(W):
    LT.update(i,i+1,i)

for i in range(H):

    a,b = AB[i]
    if a-1 >= 0:
        new = LT.query(a-1,a)
    else:
        new = float("-inf")
    LT.update(a,b+1,new)
    ST.update(a,b+1,float("inf"))
    if a-1 >= 0:
        nind = LT.query(a-1,a)
        ST.update(a-1,a,a-1-nind)
    if b+1 < W:
        nind = LT.query(b+1,b+2)
        ST.update(b+1,b+2,b+1-nind)

    ans = (ST.query(0,W)+i+1)
    if ans == float("inf"):
        print (-1)
    else:
        print (ans)

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 = defaultdict(lambda : INF)

def bfs():
    queue = []
    a,b = AB_list[1]
    dic = {i : 0 for i in range(1, W+1)}
    live_path = set(list(range(1, W+1)))

    for j in range(1, W+1):
        if a <= j <= b:
            live_path.remove(j)
            del dic[j]

    for i in range(1, H+1):
        #print(i)
        #print(queue)
        a, b = AB_list[i]
        min_move = INF
        app = 0
        ans = INF
        rm_list = []
        for v in live_path:
            ans = min(ans, dic[v]+i-1)
            move = dic[v]
            current = move + v
            if a <= current <= b:
                if b == W:
                    rm_list.append(v)
                    continue

                next_move = move + b+1-current
                if min_move > next_move:
                    min_move = next_move
                    if app:
                        rm_list.append(app)
                    app = v
                    dic[v] = next_move

                else:
                    rm_list.append(v)

        for r in rm_list:
            live_path.remove(r)
            del dic[r]

        if i > 1:
            if ans == INF:
                print(-1)
            else:
                print(ans)

    ans = INF
    for key, val in dic.items():
        ans = min(ans, val + H)

    if ans == INF:
        print(-1)
    else:
        print(ans)


def run():
    bfs()

    #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 = defaultdict(lambda : INF)

def bfs():
    queue = []
    a,b = AB_list[1]
    dic = {i : 0 for i in range(1, W+1)}
    live_path = set(list(range(1, W+1)))

    for j in range(1, W+1):
        if a <= j <= b:
            live_path.remove(j)
            del dic[j]

    for i in range(1, H+1):
        #print(i)
        #print(queue)
        a, b = AB_list[i]
        min_move = INF
        app = 0
        ans = INF
        rm_list = []
        for v in live_path:
            ans = min(ans, dic[v]+i-1)
            move = dic[v]
            current = move + v
            if a <= current <= b:
                if b == W:
                    rm_list.append(v)
                    continue

                next_move = move + b+1-current
                if min_move > next_move:
                    min_move = next_move
                    rm = app
                    app = v
                    dic[v] = next_move
                    if rm:
                        rm_list.append(rm)
                else:
                    rm_list.append(v)

        for r in rm_list:
            live_path.remove(r)
            del dic[r]

        if i > 1:
            if ans == INF:
                print(-1)
            else:
                print(ans)

    ans = INF
    for key, val in dic.items():
        ans = min(ans, val + H)

    if ans == INF:
        print(-1)
    else:
        print(ans)


def run():
    bfs()

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
dic = {}
inf = float('inf')
flag = True
for i in range(h):
  a, b = map(int, input().split())
  if i == 0:
    dic[i] = {}
    for j in range(1, a):
      dic[i][j] = 1
    for j  in range(b + 1, w + 1):
      dic[i][j] = 1
    if dic[i]:
      min_count = 1
    else:
      min_count = -1
      flag = False
  else:
    #print(dic)
    if not flag:
      min_count = -1
    else:
      con_dic = dic.pop(i - 1)
      d_set = set()
      dic[i] = {}
      min_count = inf
      for j, v in con_dic.items():
        if a <= j and j <= b:
          d_set.add(j)
        else:
          count = v + 1
          dic[i][j] = count
          if count < min_count:
            min_count = count
      if d_set and b != w:
        max_num = max(d_set)
        count = con_dic[max_num] + b - max_num + 2
        if not dic[i].get(b + 1, None):
          dic[i][b + 1] = count
        else:
          if count < dic[i][b + 1]:
            dic[i][b + 1] = count
        if count < min_count:
          min_count = count
      #print(dic[i])
      if min_count == inf:
        flag = False
        min_count = -1
  print(min_count)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
dic = {}
inf = float('inf')
flag = True
for i in range(h):
  a, b = map(int, input().split())
  if i == 0:
    dic[i] = {}
    for j in range(1, a):
      dic[i][j] = 1
    for j  in range(b + 1, w + 1):
      dic[i][j] = 1
    if dic[i]:
      min_count = 1
    else:
      min_count = -1
      flag = False
  else:
    #print(dic)
    if not flag:
      min_count = -1
    else:
      con_dic = dic.pop(i - 1)
      d_set = set()
      dic[i] = {}
      min_count = inf
      for j, v in con_dic.items():
        if a <= j and j <= b:
          d_set.add(j)
        else:
          count = v + 1
          dic[i][j] = count
          if count < min_count:
            min_count = count
      if d_set:
        max_num = max(d_set)
        if b != w:
          count = con_dic[max_num] + b - max_num + 2
          if not dic[i].get(b + 1, None):
            dic[i][b + 1] = count
          else:
            if count < dic[i][b + 1]:
              dic[i][b + 1] = count
          if count < min_count:
            min_count = count
      #print(dic[i])
      if min_count == inf:
        flag = False
        min_count = -1
  print(min_count)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
max = 4*10**5
ar = [0 for i in range(h+1)]
ar2 = [max for i in range(h+1)]
start = 1
for i in range(h):
    
    s,b = map(int,input().split())
    if start > h:
      print("-1")
      continue
    if s <= start:
        if start< b:
            start = b+1
        ar2[b] = max
    else:
        ar2[start] = ar[start]+1
    for j in range(start+1,h+1):
        if j < s or j > b:
            ar2[j] = min(ar[j]+1,ar2[j-1]+1)
        else:
            ar2[j] = ar2[j-1]+1
    res = min(ar2)
    if res >= max:
        print("-1")
        start = h+1
    else:
        print(res)
    ar = ar2

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 = defaultdict(lambda : INF)

def bfs():
    queue = []
    a,b = AB_list[1]
    for j in range(1, W+1):
        if a <= j <= b:continue
        heappush(queue, (j, 1, 0))

    for i in range(1, H+1):
        #print(i)
        #print(queue)
        ans = INF
        a, b = AB_list[i]
        next_queue = []
        while queue:
            cj, ci, count = heappop(queue)
            ans = min(ans, count)
            if cj < a:
                heappush(next_queue, (cj, ci+1, count+1))
            elif a <= cj <= b:
                if queue:
                    if a <= queue[0][0] <= b:
                        continue
                else:
                    if W >= b+1:
                        heappush(next_queue, (b+1, ci+1, count + b+2-cj))
            else:
                heappush(next_queue, (cj+1, ci, count+1))
        if i > 1:
            if ans == INF:
                print(-1)
            else:
                print(ans)
        queue = next_queue
    ans = INF
    while queue:
        _, _, count = heappop(queue)
        ans = min(ans, count)

    if ans == INF:
        print(-1)
    else:
        print(ans)


def run():
    bfs()

    #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 = defaultdict(lambda : INF)

def bfs():
    queue = []
    for j in range(1, W+1):
        heappush(queue, (j, 1, 0))

    for i in range(1, H+1):
        #print(i)
        #print(queue)
        ans = INF
        a, b = AB_list[i]
        next_queue = []
        while queue:
            cj, ci, count = heappop(queue)
            ans = min(ans, count)
            if cj < a:
                heappush(next_queue, (cj, ci+1, count+1))
            elif a <= cj <= b:
                if queue:
                    if a <= queue[0][0] <= b:
                        continue
                else:
                    if W >= b+1:
                        heappush(next_queue, (b+1, ci+1, count + b+2-cj))
            else:
                heappush(next_queue, (cj+1, ci, count+1))
        if i > 1:
            if ans == INF:
                print(-1)
            else:
                print(ans)
        queue = next_queue
    ans = INF
    while queue:
        _, _, count = heappop(queue)
        ans = min(ans, count)

    if ans == INF:
        print(-1)
    else:
        print(ans)


def run():
    bfs()

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
dic = {}
inf = float('inf')
flag = True
for i in range(h):
  a, b = map(int, input().split())
  if i == 0:
    dic[i] = {}
    for j in range(1, a):
      dic[i][j] = 1
    for j  in range(b + 1, w + 1):
      dic[i][j] = 1
    if dic[i]:
      min_count = 1
    else:
      min_count = -1
      flag = False
  else:
    #print(dic)
    if not flag:
      min_count = -1
    else:
      con_dic = dic.pop(i - 1)
      d_set = set()
      dic[i] = {}
      min_count = inf
      for j, v in con_dic.items():
        if a <= j and j <= b:
          d_set.add(j)
        else:
          count = v + 1
          dic[i][j] = count
          if count < min_count:
            min_count = count
      if d_set:
        max_num = max(d_set)
        k = b + 1
        if b == w:
          count = inf
        else:
          count = con_dic[max_num] + b - max_num + 2
          if count < min_count:
            min_count = count
          dic[i][k] = count
      #print(dic[i])
      if min_count == inf:
        flag = False
        min_count = -1
  print(min_count)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
dic = {}
inf = float('inf')
flag = True
for i in range(h):
  a, b = map(int, input().split())
  if i == 0:
    dic[i] = {}
    for j in range(1, a):
      dic[i][j] = 1
    for j  in range(b + 1, w + 1):
      dic[i][j] = 1
    if dic[i]:
      count = 1
    else:
      count = -1
      flag = False
  else:
    #print(dic)
    if not flag:
      count = -1
    else:
      con_dic = dic.pop(i - 1)
      d_set = set()
      dic[i] = {}
      min_count = inf
      for j, v in con_dic.items():
        if a <= j and j <= b:
          d_set.add(j)
        else:
          count = v + 1
          dic[i][j] = count
          if count < min_count:
            min_count = count
      if d_set:
        max_num = max(d_set)
        k = b + 1
        if b == w:
          count = inf
        else:
          count = con_dic[max_num] + b - max_num + 2
          if count < min_count:
            min_count = count
          dic[i][k] = count
      #print(dic[i])
      if min_count == inf:
        flag = False
        count = -1
      else:
        count = min_count
  print(count)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
dic = {}
dic2 = {}
inf = float('inf')
flag = True
for i in range(h):
  a, b = map(int, input().split())
  if i == 0:
    dic[i] = {}
    for j in range(1, a):
      dic[i][j] = 1
    for j  in range(b + 1, w + 1):
      dic[i][j] = 1
    if dic[i]:
      count = 1
    else:
      count = -1
      flag = False
  else:
    #print(dic)
    if not flag:
      count = -1
    else:
      con_dic = dic.pop(i - 1)
      d_set = set()
      dic[i] = {}
      min_count = inf
      for j, v in con_dic.items():
        if a <= j and j <= b:
          d_set.add(j)
        else:
          count = v + 1
          dic[i][j] = count
          if count < min_count:
            min_count = count
      if d_set:
        max_num = max(d_set)
        k = b + 1
        if b == w:
          count = inf
        else:
          count = con_dic[max_num] + b - max_num + 2
          if count < min_count:
            min_count = count
        dic[i][k] = count
      #print(dic[i])
      if min_count == inf:
        flag = False
        count = -1
      else:
        count = min_count
  print(count)