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 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 << 20
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 = 1 << 18
st1 = SegmentTree([-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), 0, -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)
    print(st2.X[1] + i + 1 if st2.X[1] < 1 << 19 else -1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
AB = [[int(i) - 1 for i in input().split()] for _ in range(H)]

ret = [float('inf')] * H
last = [-1] * H
for dx in range(W - 1, -1, -1) :
  x = dx
  for y in range(H) :
    if AB[y][0] <= x <= AB[y][1] :
      if AB[y][1] == W - 1 :
        break
      else :
        x = AB[y][1] + 1
    if last[y] == x :
      break
    last[y] = x
    ret[y] = min(ret[y], x - dx + 1 + y)
    
for y in range(H) :
  if ret[y] == float('inf') :
    print(-1)
  else :
    print(ret[y])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 遅延評価セグメントツリー
## 更新：区間の値をxに更新する　　クエリ演算：op (min, max)
## 0-indexed
class LazySegmentTree:
    def __init__(self,N,default=float('inf')):
        # 演算の定義
        self.op = min
        # 初期化の値
        self.default = default
        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.default]*(2*self.N0)
        self.lazy = [None]*(2*self.N0)

    #伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self,l,r):
        L = l + self.N0; R = r + self.N0
        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

    # 1-indexedで単調増加のインデックスリストを渡す
    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.tree[2*i-1] = self.lazy[2*i] = self.tree[2*i] = v
            self.lazy[i-1] = None

    # 区間[l,r)の値をxに更新
    def update(self,l,r,x):
        if l < r:
            *ids, = self.gindex(l, r)
            self.propagates(*ids)

            L = l + self.N0; R = r + self.N0
            while L < R:
                if R & 1:
                    R -= 1
                    self.lazy[R-1] = self.tree[R-1] = x
                if L & 1:
                    self.lazy[L-1] = self.tree[L-1] = x
                    L += 1
                L >>= 1; R >>= 1

            for i in ids:
                self.tree[i-1] = self.op(self.tree[2*i-1], self.tree[2*i])

    # 区間[l,r)へのクエリ
    def query(self,l,r):
        self.propagates(*self.gindex(l, r))
        L = l + self.N0; R = r + self.N0
        s = self.default
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s,self.tree[R-1])
            if L & 1:
                s = self.op(s,self.tree[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    # a[k]を取得
    def get(self,k):
        self.propagates(*self.gindex(k, k+1))
        return self.tree[k+self.N0-1]

H,W = LI()
A,B = LIR(H,2)
for i in range(H):
    A[i] -= 1
    B[i] -= 1

inf = 2**51-1
seg = LazySegmentTree(W,inf)
seg.update(0,W,0)
ans = []
for i in range(H):
    if A[i] == 0:
        seg.update(0,B[i]+1,inf)
    else:
        val = seg.get(A[i]-1)
        for j in range(A[i],B[i]+1):
            seg.update(j,j+1,val+j)
    ans.append(seg.query(0,W)+i+1)
    #print([seg.get(j) for j in range(W)],seg.query(0,W))

for a in ans:
    if a > 2**30:
        print(-1)
    else:
        print(a)

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 + 2 - 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)
		# print(lSeg.data[3:])
		if ans == INF:
			print(-1)
		else:
			print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, raw_input().split())
dp = [0 for ii in range(w)]
m = -1
for _ in range(h):
	if m == float('inf'):
		print -1
		continue
	ai,bi = map(lambda x:int(x) -1, raw_input().split())
	for j in range(w):
		dp[j] = min(+float('inf'), 1 + (dp[j] if not(ai<=j <=bi) else +float('inf')), 1+ (dp[j-1]  if j-1 >= 0 else +float('inf')))
	m = min(dp) 
	print m if m < float('inf') else -1

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(h)]

# 貪欲でシミュレーション

inf = 10 ** 19

ans = [inf] * h
for i in range(1, w + 1):
  pos = i
  steps = 0
  downable = True
  for itr, (a, b) in enumerate(AB):
    if not downable:
      ans[itr] = min(ans[itr], inf)
    else:
      if pos < a or b < pos:
        steps += 1
        ans[itr] = min(ans[itr], steps)
      elif a <= pos <= b:
        steps += b - pos + 2 # 右へ：b - pos + 1、下へ1
        pos = b + 1
        if b >= w:
          ans[itr] = min(ans[itr], inf)
          downable = False
        else:
          ans[itr] = min(ans[itr], steps)

for an in ans:
  print(-1 if an == inf else an)

Submission status: Time Limit Exceeded

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


def solve(H: int, W: int, A: "List[int]", B: "List[int]"):
    INF = float("inf")
    C = [range(a, b) for a, b in zip(A, B)]
    dp = [[INF] * W for _ in range(H+1)]
    dp[0] = [0] * W
    for h in range(H):
        for w in range(W):
            if (w + 1) < W:
                dp[h][w+1] = min(dp[h][w+1], dp[h][w]+1)
            if not (A[h] <= (w+1) <= B[h]):
                dp[h+1][w] = min(dp[h+1][w], dp[h][w]+1)
    ans = [min(d) for d in dp[1:]]
    ans = [d if d != INF else -1 for d in ans]
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [int()] * (H)  # type: "List[int]"
    B = [int()] * (H)  # type: "List[int]"
    for i in range(H):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    print(*solve(H, W, A, B), sep="\n")

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
N = 0
A = [0 for i in range(W)]
for i in range(H):
  a, b = map(int, input().split())
  B = [400000 for i in range(W)]
  p = 0
  for j in range(N, W):
    if p == 0 and (a - 1 > j or j > b - 1):
      N = j
      B[j] = A[j] + 1
      p = 1
    if p == 1:
      B[j] = B[j-1] + 1
      if a - 1 > j or j > b - 1:
        B[j] = min(A[j] + 1, B[j])
  m = min(B)
  if m != 400000:
    print(m)
  else:
    print(-1)
  A = B

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, raw_input().split())
dp = [0 for ii in range(w)]
for _ in range(h):
	ai,bi = map(lambda x:int(x) -1, raw_input().split())
	dpp = [+float('inf') for ii in range(w)]
	for j in range(w):
		dpp[j] = min(dpp[j], 1 + (dp[j] if not(ai<=j <=bi) else +float('inf')), 1+ (dpp[j-1]  if j-1 >= 0 else +float('inf')))
	dp = dpp[::]
	m = min(dp) 
	print m if m < float('inf') else -1

Submission status: Time Limit Exceeded

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

MAX=10**19

dp=[[0]*W for _ in range(2)]
for h in range(H):
    a,b=[int(e)-1 for e in input().split()]
    for w in range(W):
        l=[MAX]
        if w>0:
            l.append(dp[(h+1)%2][w-1]+1)
        if not(a<=w<=b):
            l.append(dp[h%2][w]+1)
        dp[(h+1)%2][w]=min(l)
    ans=min(dp[(h+1)%2])
    if ans == MAX:
        print(-1)
    else:
        print(ans)

Submission status: Time Limit Exceeded

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

AB = [list(map(int,input().split())) for i in range(H)]

ans = [10**15]*(H)

for x in range(1,W+1):
    cost=0
    for i in range(H):
        a,b = AB[i]
        if a<=x and x<=b:
            cost+=b-x+1
            x=b+1
            if x > W:
                break
        cost+=1
        ans[i] = min(ans[i],cost)


for i in range(len(ans)):
    if ans[i]==10**15:
        ans[i]=-1
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=min(seg[2*i+1],seg[2*i+2])


def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = min(seg[k*2+1],seg[k*2+2])


def query(p,q): # pからq-1までの最大値
    if q<=p:
        return INF
    p += num-1
    q += num-2
    res=INF
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg[p])
        if q&1 == 1:
            res = min(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg[p])
    else:
        res = min(min(res,seg[p]),seg[q])
    return res


h, w = map(int,input().split())

a = [0] * w
n = len(a)

#num:n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
INF = 2**31-1
seg = [INF]*(2*num)

init(a)
ab = [list(map(int,input().split())) for i in range(h)]

for i in range(h):
    l, r = ab[i][0]-1, ab[i][1]-1
    for c in range(w):
        if c < l or r < c:
            update(c,seg[c+num-1] + 1)
        elif c > 0 and seg[c+num-2] < INF:
            update(c,seg[c+num-2]+1)
        else:
            update(c,INF)
    print(seg[0]) if seg[0] < INF else print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    obstacle = [list(map(int, input().split())) for _ in range(H)]
    i_max = 0
    for y in range(1, W+1):
        y = 1
        t = 0
        ans = [-1] * H
        for i in range(H):
            A, B = obstacle[i]
            if y < A or y > B:
                t += 1
            else:
                t += B - y + 2
                y = B + 1
                if y > W:
                    break
            ans[i] = t
        if i < i_max:
            break
        else:
            i_max = i
    for i in range(H):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def main():
    H, W = map(int, input().split())
    adj = [[] for _ in range(W*H)]
    dx = [1,0]
    dy = [0,1]
    
    for i in range(H):
        a, b = map(lambda x: int(x)-1, input().split())
        for j in range(W):
            y = i
            x = j+1
            if x < W:
                adj[W*i + j].append(W*y + x)
        if i < H:
            jl = [*range(a)] + [*range(b+1,W)]
            # print(a,b,jl)
            for j in jl:
                y = i+1
                x = j
                if 0 <= y < H:
                    adj[W*i + j].append(W*y + x)

    # print(adj)
    ans = 0
    now = 0
    for i in range(H):
        if i == H-1: 
            print(-1)
        else:
            while 1:
                if now+W in adj[now]:# 今下に降りれる
                    now += W
                    ans += 1
                    print(ans)
                    break
                else:
                    now += 1
                    ans += 1
                    if now%W == 0:# 降りれず右まで来てしまった
                        for j in range(i,H):
                            print(-1)
                        exit(0)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

INF = 10 ** 6
H, W = map(int,input().split())
A = []
B = []
for i in range(H):
    a, b = map(int,input().split())
    A.append(a-1)
    B.append(b-1)

ans = [-1 for _ in range(H * W)]
ans2 = [INF] * H

def dfs(x, y, cnt, cnt2):
    if x != 0 and ans[(x-1) * W + y] != -1 and ans[(x-1) * W + y] <= cnt - cnt2:
        return
    if x != 0 and (ans[(x-1) * W + y] == -1 or ans[(x-1) * W + y] > cnt - cnt2):
        ans[(x-1) * W + y] = cnt - cnt2
        ans2[x-1] = min(ans2[x-1], cnt - cnt2)
    if x == H:
        for i in ans2:
            if i == INF:
                print(-1)
            else:
                print(i)
        sys.exit()
    nx = x + 1
    ny = y
    if not A[x] <= ny <= B[x]:
        dfs(nx, ny, cnt + 1, cnt2)
    else:
        nx = x
        ny = y + 1
        if ny < W:
            if nx == 0:
                cnt2 += 1
            dfs(nx, ny, cnt + 1, cnt2)

dfs(0, 0, 0, 0)

for i in ans2:
    if i == INF:
        print(-1)
    else:
        print(i)

Submission status: Time Limit Exceeded

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

def main():
    H, W = map(int, input().split())
    
    adj = [[] for _ in range(W*H)]
    dx = [1,0]
    dy = [0,1]
    
    for i in range(H):
        a, b = map(lambda x: int(x)-1, input().split())
        for j in range(W):
            if a <= j <= b:
                ks = [0]
            else:
                ks = [0,1]
            for k in ks:
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W:
                    adj[W*i + j].append(W*y + x)

    ans = 0
    now = 0
    for i in range(H):
        if i == H-1: 
            print(-1)
        else:
            while 1:
                if now+W in adj[now]:# 今下に降りれる
                    now += W
                    ans += 1
                    print(ans)
                    break
                else:
                    now += 1
                    ans += 1
                    if now%W == 0:# 降りれず右まで来てしまった
                        for j in range(i,H):
                            print(-1)
                        exit(0)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

INF = 10 ** 6
H, W = map(int,input().split())
A = []
B = []
for i in range(H):
    a, b = map(int,input().split())
    A.append(a-1)
    B.append(b-1)

ans = [-1 for _ in range(H * W)]
ans2 = [INF] * H

def dfs(x, y, cnt, cnt2):
    if x != 0 and ans[(x-1) * W + y] != -1 and ans[(x-1) * W + y] <= cnt - cnt2:
        return
    if x != 0 and (ans[(x-1) * W + y] == -1 or ans[(x-1) * W + y] > cnt - cnt2):
        ans[(x-1) * W + y] = cnt - cnt2
        ans2[x-1] = min(ans2[x-1], cnt - cnt2)
    if x == H:
        for i in ans2:
            if i == INF:
                print(-1)
            else:
                print(i)
        sys.exit()
    nx = x
    ny = y + 1
    if ny < W:
        if nx == 0:
            dfs(nx, ny, cnt + 1, cnt2 + 1)
        else:
            dfs(nx, ny, cnt + 1, cnt2)
    nx = x + 1
    ny = y
    if not A[x] <= ny <= B[x]:
        dfs(nx, ny, cnt + 1, cnt2)

dfs(0, 0, 0, 0)

for i in ans2:
    if i == INF:
        print(-1)
    else:
        print(i)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

INF = 10 ** 6
H, W = map(int,input().split())
A = []
B = []
for i in range(H):
    a, b = map(int,input().split())
    A.append(a-1)
    B.append(b-1)

ans = [-1 for _ in range(H * W)]
ans2 = [INF] * H

def dfs(x, y, cnt, cnt2):
    if x != 0 and ans[(x-1) * W + y] != -1 and ans[(x-1) * W + y] <= cnt - cnt2:
        return
    if x != 0 and (ans[(x-1) * W + y] == -1 or ans[(x-1) * W + y] > cnt - cnt2):
        ans[(x-1) * W + y] = cnt - cnt2
        ans2[x-1] = min(ans2[x-1], cnt - cnt2)
    if x == H:
        for i in ans2:
            if i == INF:
                print(-1)
            else:
                print(i)
        sys.exit()
    nx = x + 1
    ny = y
    if not A[x] <= ny <= B[x]:
        dfs(nx, ny, cnt + 1, cnt2)
    nx = x
    ny = y + 1
    if ny < W:
        if nx == 0:
            cnt2 += 1
        dfs(nx, ny, cnt + 1, cnt2)

dfs(0, 0, 0, 0)

for i in ans2:
    if i == INF:
        print(-1)
    else:
        print(i)

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(h)]
past = defaultdict(lambda: defaultdict(lambda: False))
INF = 10**9+7
ans = [INF for _ in range(h)]
# 貪欲
for start_i in range(w, 0, -1):
    cur_i = start_i
    cost = 0
    for row_num in range(h):
        a, b = ab[row_num]
        if a <= cur_i <= b:
            cost += (b + 1 - cur_i)
            cur_i = b + 1
        if cur_i > w:
            break
        if past[row_num+1][cur_i]:
            break
        else:
            cost += 1
            ans[row_num] = min(ans[row_num], cost)
            past[row_num+1][cur_i] = True

for i in range(len(ans)):
    if ans[i] == INF:
        ans[i] = -1
print("\n".join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
""" F
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(H, W, M):
    c = 0
    x = 0 if M[0][0] > 0 else M[0][1] + 1
    for k in range(H):
        if x > W-1:
            print(-1)
            continue
        if x >= M[k][0]-1 and x <= M[k][1]-1:
            x0 = x
            x = M[k][1]
            if x > W-1:
                print(-1)
                continue
            c += (x - x0 + 1)
        else:
            c += 1
        print(c)



if __name__ == "__main__":
    _H, _W = readIntegerSet(2)
    _M = readIntegerMatrix(_H, 2)

    main(_H, _W, _M)

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(h)]
pasted = defaultdict(lambda: defaultdict(lambda: False))
INF = 10**9+7
ans = [INF for _ in range(h)]
# 貪欲
for start_i in range(w, 0, -1):
    cur_i = start_i
    cost = 0
    for row_num in range(h):
        a, b = ab[row_num]
        if a <= cur_i <= b:
            cost += (b + 1 - cur_i)
            cur_i = b + 1
        if cur_i <= w:
            cost += 1
            ans[row_num] = min(ans[row_num], cost)
        else:
            break
        if pasted[row_num+1, cur_i]:
            break
        else:
            pasted[row_num+1, cur_i] = True

for i in range(len(ans)):
    if ans[i] == INF:
        ans[i] = -1
print("\n".join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

INF = 10 ** 6
H, W = map(int,input().split())
A = []
B = []
for i in range(H):
    a, b = map(int,input().split())
    A.append(a-1)
    B.append(b-1)

ans = [[-1 for i in range(W)] for j in range(H)]
ans2 = [INF] * H

def dfs(x, y, cnt, cnt2):
    if x != 0 and ans[x-1][y] != -1 and ans[x-1][y] <= cnt - cnt2:
        return
    if x != 0 and (ans[x-1][y] == -1 or ans[x-1][y] > cnt - cnt2):
        ans[x-1][y] = cnt - cnt2
        ans2[x-1] = min(ans2[x-1], cnt - cnt2)
    if x == H:
        for i in ans2:
            if i == INF:
                print(-1)
            else:
                print(i)
        sys.exit()
    nx = x + 1
    ny = y
    if not A[x] <= ny <= B[x]:
        dfs(nx, ny, cnt + 1, cnt2)
    nx = x
    ny = y + 1
    if ny < W:
        if nx == 0:
            cnt2 += 1
        dfs(nx, ny, cnt + 1, cnt2)

dfs(0, 0, 0, 0)

for i in ans2:
    if i == INF:
        print(-1)
    else:
        print(i)

Submission status: Time Limit Exceeded

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

h,w = map(int,input().split())

x = 1
A = []
B = []
kouho = [1]
for i in range(h):
    AA,BB = map(int,input().split())
    A.append(AA)
    B.append(BB)
    if i <= 100 or i%1000:
        kouho.append(AA)
        kouho.append(BB)


dp = [10**6] * h
for start in kouho:
    x = start
    for i in range(h):
        a,b = A[i],B[i]
        if a <= x <= b:
            x = b+1
        if x != w+1:
            dp[i] = min(dp[i],x+i)

for i in range(h):
    if dp[i] == 10**6:
        print(-1)
    else:
        print(dp[i])

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
MAX=H*W+1

prev=[0]*(W+1)
for i in range(H):
    A,B=map(lambda x:int(x),input().split())
    DP=[MAX]*(W+1)
    for i in range(1,W+1):#ここをどうにかする。
        if A<=i<=B:
            DP[i]=DP[i-1]+1
        else:
            DP[i]=prev[i]+1
    prev=DP
    min_prev=min(prev)
    if min_prev==MAX:
        print(-1)
    else:
        print(min_prev)

Submission status: Time Limit Exceeded

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

mod = int(1e9) + 7

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