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 = 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)
      dic[i] = {}
      min_count = inf
      for j, v in con_dic.items():
        if a <= j and j <= b:
          if b != w:
            count = v + b - j + 2
            k = b + 1
          else:
            count = inf
            k = w + 1
        else:
          count = v + 1
          k = j
        if k == b + 1:
          if not dic[i].get(k, None):
            dic[i][k] = count
          elif count < dic[i][k]:
            dic[i][k] = count
        else:
          dic[i][k] = count
        if count < min_count:
          min_count = 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:
# 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)
done = [0] * (H+2)

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

    while queue:
        count, ci, cj = heappop(queue)
        if MAP[(ci, cj)] <= count:
            continue
        else:
            MAP[(ci, cj)] = count
        if not done[ci]:
            min_list[ci] = count



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

        if a <= cj <= b:
            if b + 1 <= W:
                ni = ci + 1
                nj = b + 1
                nc = count + b - cj + 2
                heappush(queue, (nc, ni, nj))

        elif ci + 1 <= H+1:
            ni = ci + 1
            nj = cj
            nc = count + 1
            heappush(queue, (nc, ni, nj))


def run():
    bfs()

    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 = defaultdict(lambda : INF)
done = [0] * (H+2)

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

    while queue:
        count, ci, cj = heappop(queue)
        if not done[ci]:
            min_list[ci] = count

        if MAP[(ci, cj)] <= count:
            continue
        else:
            MAP[(ci, cj)] = count

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

        if a <= cj <= b:
            if b + 1 <= W:
                ni = ci + 1
                nj = b + 1
                nc = count + b - cj + 2
                heappush(queue, (nc, ni, nj))

        elif ci + 1 <= H+1:
            ni = ci + 1
            nj = cj
            nc = count + 1
            heappush(queue, (nc, ni, nj))


def run():
    bfs()

    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 = defaultdict(lambda : INF)
done = [0] * (H+2)

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

    while queue:
        count, ci, cj = heappop(queue)
        if not done[ci]:
            min_list[ci] = count

        if MAP[(ci, cj)] < count:
            continue
        else:
            MAP[(ci, cj)] = count

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

        if a <= cj <= b:
            if b + 1 <= W:
                ni = ci + 1
                nj = b + 1
                nc = count + b - cj + 2
                heappush(queue, (nc, ni, nj))

        elif ci + 1 <= H+1:
            ni = ci + 1
            nj = cj
            nc = count + 1
            heappush(queue, (nc, ni, nj))


def run():
    bfs()

    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 = defaultdict(lambda : INF)
done = [0] * (H+2)

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

    while queue:
        count, ci, cj = heappop(queue)
        if not done[ci]:
            min_list[ci] = count

        if MAP[(ci, cj)] < count:
            continue
        else:
            MAP[(ci, cj)] = count

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

        if a <= cj <= b:
            if b + 1 <= W:
                ni = ci + 1
                nj = b + 1
                nc = count + b - cj + 2
                if MAP[(ni, nj)] > nc:
                    MAP[(ni, nj)] = nc
                    heappush(queue, (nc, ni, nj))

        elif ci + 1 <= H+1:
            ni = ci + 1
            nj = cj
            nc = count + 1
            if MAP[(ni, nj)] > nc:
                MAP[(ni, nj)] = nc
                heappush(queue, (nc, ni, nj))


def run():
    bfs()

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

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

    while queue:
        ci, cj, count = queue.popleft()
        if MAP[(ci, cj)] < count:
            continue
        min_list[ci] = min(min_list[ci], count)

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

        if a <= cj <= b:
            if b + 1 <= W:
                ni = ci + 1
                nj = b + 1
                nc = count + b - cj + 2
                if MAP[(ni, nj)] > nc:
                    MAP[(ni, nj)] = nc
                    queue.append((ni, nj, nc))

        elif ci + 1 <= H+1:
            ni = ci + 1
            nj = cj
            nc = count + 1
            if MAP[(ni, nj)] > nc:
                MAP[(ni, nj)] = nc
                queue.append((ni, nj, nc))


def run():
    bfs()

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

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

    while queue:
        ci, cj, count = queue.popleft()
        if MAP[(ci, cj)] < count:
            continue
        min_list[ci] = min(min_list[ci], count)

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

        if a <= cj <= b:
            if b + 1 <= W:
                ni = ci + 1
                nj = b + 1
                nc = count + b - cj + 2
                if MAP[(ni, nj)] > nc:
                    MAP[(ni, nj)] = nc
                    queue.append((ni, nj, nc))

        elif ci + 1 <= H+1:
            ni = ci + 1
            nj = cj
            nc = count + 1
            if MAP[(ni, nj)] > nc:
                MAP[(ni, nj)] = nc
                queue.append((ni, nj, nc))


def run():
    bfs()

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

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

    while queue:
        ci, cj, count = queue.popleft()
        if MAP[(ci, cj)] < count:
            continue

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

        if a <= cj <= b:
            if b + 1 <= W:
                ni = ci + 1
                nj = b + 1
                nc = count + b - cj + 2
                MAP[(ni, nj)] = min(MAP[(ni, nj)], nc)
                min_list[ni] = min(min_list[ni], nc)
                queue.append((ni, nj, nc))

        elif ci + 1 <= H+1:
            ni = ci + 1
            nj = cj
            nc = count + 1
            MAP[(ni, nj)] = min(MAP[(ni, nj)], nc)
            min_list[ni] = min(min_list[ni], nc)
            queue.append((ni, nj, nc))


def run():
    bfs()

    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 numpy as np
INF = 10**9
H, W = map(int, input().split())
walls = [tuple(map(int, input().split())) for _ in range(H)]
memo = np.zeros(W+1, dtype=np.int64) # 1インデックス
memo[0] = INF

count = 0
for wall in walls:
    start, end = wall
    memo += 1
    memo[start:end+1] = 0
    for i in range(start, end+1):
        if memo[i] == 0:
            memo[i] += memo[i-1] + 1
    count = min(memo)
    if count >= INF:
        print(-1)
    else:
        print(count)

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(start):
    queue = deque([(start + (0,))])
    while queue:
        ci, cj, count = queue.popleft()
        if MAP[(ci, cj)] < count:
            continue

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

        if a <= cj <= b:
            if b + 1 <= W:
                ni = ci + 1
                nj = b + 1
                nc = count + b - cj + 2
                MAP[(ni, nj)] = min(MAP[(ni, nj)], nc)
                min_list[ni] = min(min_list[ni], nc)
                queue.append((ni, nj, nc))

        elif ci + 1 <= H+1:
            ni = ci + 1
            nj = cj
            nc = count + 1
            MAP[(ni, nj)] = min(MAP[(ni, nj)], nc)
            min_list[ni] = min(min_list[ni], nc)
            queue.append((ni, nj, nc))


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

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

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

        if a <= cj <= b:
            if b + 1 <= W:
                ni = ci + 1
                nj = b + 1
                nc = count + b - cj + 2
                MAP[(ci, cj)] = min(MAP[(ci, cj)], nc)
                queue.append((ni, nj, nc))

        elif ci + 1 <= H+1:
            ni = ci + 1
            nj = cj
            nc = count + 1
            MAP[(ci, cj)] = min(MAP[(ci, cj)], nc)
            queue.append((ni, nj, nc))


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

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

        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)//2 + 1):
        if a1 <= j <= b1:continue
        bfs((1, j))
        bfs((1, W+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 numpy as np
INF = 10**9
H, W = map(int, input().split())
walls = [tuple(map(int, input().split())) for _ in range(H)]
memo = np.zeros(W+1, dtype=np.int64) # 1インデックス
memo[0] = INF

for wall in walls:
    start, end = wall

    memo += 1
    memo[start:end+1] = 0
    for i in range(1, W+1):
        if memo[i] == 0:
            memo[i] += memo[i-1] + 1

    count = min(memo)
    if count >= INF:
        print(-1)
    else:
        print(count)

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
            if min_list[ci] > count:
                min_list[ci] = count
        else:
            continue

        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)//2 + 1):
        if a1 <= j <= b1:continue
        bfs((1, j))
        bfs((1, W+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
            if min_list[ci] > count:
                min_list[ci] = count
        else:
            continue



        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:
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:
      dic[i] = {}
      min_count = inf
      for j, v in dic[i - 1].items():
        if a <= j and j <= b:
          if b != w:
            count = v + b - j + 2
            k = b + 1
          else:
            count = inf
            k = w + 1
        else:
          count = v + 1
          k = j
        if k == b + 1:
          if not dic[i].get(k, None):
            dic[i][k] = count
          if count < dic[i][k]:
            dic[i][k] = count
        else:
          dic[i][k] = count
        if count < min_count:
          min_count = count
      #print(dic[i])
      #_ = dic.pop(i - 1)
      if min_count == inf:
        flag = False
        count = -1
      else:
        count = min_count
  print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    H, W = list(map(int, input().split()))
    constraints = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(H)]
    start2cur = {i: i for i in range(W)}
    ans = [-1] * H
    for h in range(H):
        a, b = constraints[h]
        starts_with_same_curs = list()
        min_w = W
        for start in start2cur.keys():
            cur = start2cur[start]
            if a <= cur <= b:
                cur = b + 1
                starts_with_same_curs.append(start)
            if cur < W:
                min_w = min(min_w, cur - start)
            start2cur[start] = cur
        if min_w < W:
            ans[h] = h + 1 + min_w
        if b == W - 1:
            # 横にはみ出るものを全部消す
            for s in starts_with_same_curs:
                del start2cur[s]
        elif len(starts_with_same_curs) > 1:
            # 同じ行先になるもののうち、始点が一番右のもの以外を消す
            for s in starts_with_same_curs[:-1]:
                del start2cur[s]
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, OrderedDict


def main():
    H, W = list(map(int, input().split()))
    constraints = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(H)]
    start2cur = OrderedDict([(i, i) for i in range(W)])
    ans = [-1] * H
    for h in range(H):
        a, b = constraints[h]
        starts_with_same_curs = list()
        min_w = W
        for start in start2cur.keys():
            cur = start2cur[start]
            if a <= cur <= b:
                cur = b + 1
                starts_with_same_curs.append(start)
            if cur < W:
                min_w = min(min_w, cur - start)
            start2cur[start] = cur
        if min_w < W:
            ans[h] = h + 1 + min_w
        if b == W - 1:
            # 横にはみ出るものを全部消す
            for s in starts_with_same_curs:
                del start2cur[s]
        elif len(starts_with_same_curs) > 1:
            # 同じ行先になるもののうち、始点が一番右のもの以外を消す
            for s in starts_with_same_curs[:-1]:
                del start2cur[s]
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

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:
      dic[i] = {}
      min_count = inf
      for j, v in dic[i - 1].items():
        if a <= j and j <= b:
          if b != w:
            count = v + b - j + 2
            k = b + 1
          else:
            count = inf
            k = w + 1
        else:
          count = v + 1
          k = j
        if k == b + 1:
          if not dic[i].get(k, None):
            dic[i][k] = count
          if count < dic[i][k]:
            dic[i][k] = count
        else:
          dic[i][k] = count
        if count < min_count:
          min_count = count
      #print(dic[i])
      _ = dic.pop(i - 1)
      if min_count == inf:
        flag = False
        count = -1
      else:
        count = min_count
  print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, OrderedDict


def main():
    H, W = list(map(int, input().split()))
    constraints = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(H)]
    start2cur = OrderedDict([(i, i) for i in range(W)])
    ans = [-1] * H
    for h in range(H):
        a, b = constraints[h]
        starts_with_same_curs = list()
        min_w = W
        for start in start2cur.keys():
            cur = start2cur[start]
            if a <= cur <= b:
                cur = b + 1
                starts_with_same_curs.append(start)
            if cur < W:
                min_w = min(min_w, cur - start)
            start2cur[start] = cur 
        if min_w < W:
            ans[h] = h + 1 + min_w
        if b == W - 1:
            # 横にはみ出るものを全部消す
            for s in starts_with_same_curs:
                start2cur.pop(s)
        elif len(starts_with_same_curs) > 1:
            # 同じ行先になるもののうち、始点が一番右のもの以外を消す
            for s in starts_with_same_curs[:-1]:
                start2cur.pop(s)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, OrderedDict


def main():
    H, W = list(map(int, input().split()))
    constraints = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(H)]
    start2cur = OrderedDict([(i, i) for i in range(W)])
    ans = [-1] * H
    for h in range(H):
        a, b = constraints[h]
        cur2start = defaultdict(list)
        min_w = W
        for start in start2cur.keys():
            cur = start2cur[start]
            if a <= cur <= b:
                cur = b + 1
            if cur < W:
                min_w = min(min_w, cur - start)
            start2cur[start] = cur 
            cur2start[cur].append(start)
        if min_w < W:
            ans[h] = h + 1 + min_w
        for cur, start_list in cur2start.items():
            # 行先が横にはみ出してしまうものを消す
            if cur >= W:
                for s in start_list:
                    start2cur.pop(s)
                continue
            if len(start_list) <= 1:
                continue
            # 同じ行先になるもののうち、始点が一番右のもの以外を消す
            for s in start_list[:-1]:
                start2cur.pop(s)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()