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: Runtime Error

Solution code:
from heapq import *


class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
    counter が与えられなかった場合は、全て個数 0 で初期化される。
    閉区間で管理する。
    """

    __slots__ = ["n", "k", "data"]

    def __init__(self, maxvalue, counter = None):
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)
        if counter is not None:
            self.update(counter)
        
    def update(self, counter):
        """
        counter を受け取って、それを反映させる。
        counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
        計算量は、n を要素の最大値として、 O(n) となる。
        """
        if isinstance(counter, list):
            self.data = [0] + counter + [0] * (self.n - len(counter))
        else:
            self.data = [0] * (self.n + 1)
            for k, v in counter.items():
                self.data[k + 1] = v
        for i in range(1, self.n + 1):
            if i + (i & -i) <= self.n:
                self.data[i + (i & -i)] += self.data[i]

    def add(self, value):
        """
        与えられた引数を Multiset に加える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] += 1
            value += value & -value

    def pop(self, value):
        """
        Multiset から与えられた引数を取り除く。
        与えられた引数が Multiset に入っているかのチェックは行わなず、
        単にその個数を 1 減らすだけなので注意。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] -= 1
            value += value & -value

    def count_le(self, value):
        """
        Multiset 内の要素 elem のうち、0 <= elem <= value を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        ret = 0
        while value > 0:
            ret += self.data[value]
            value -= value & -value
        return ret

    def count(self, first, last):
        """
        Multiset 内の要素 elem のうち、first <= elem <= last を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        last += 1
        ret = 0
        while first < last:
            ret += self.data[last]
            last -= last & -last
        while last < first:
            ret -= self.data[first]
            first -= first & -first
        return ret

    def bisect(self, count):
        """
        Multiset 内の要素 elem のうち、count <= count_le(elem) を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        ret = 0
        k = self.k
        while k > 0:
            if ret + k <= self.n and self.data[ret + k] < count:
                count -= self.data[ret + k]
                ret += k
            k //= 2
        return ret


    def lower_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value <= elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value - 1) + 1)

    def upper_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value < elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value) + 1)


H, W = map(int, input().split())

destination = MultisetBIT(W, {i:1} for _ in range(W))

destination_to_cost = {i:0 for i in range(W)}

min_heapq = [0] * W
to_delete = []

for k in range(H):
    # print([i for i in range(W) if destination.count(i, i)])
    # print(destination_to_cost)
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    start_point = destination.lower_bound(A)
    point = start_point
    change_dest_flg = False
    while point < W and point < B + 1:
        change_dest_flg = True
        cost = destination_to_cost.pop(point)
        heappush(to_delete, cost)
        if B + 1 != W:
            if (B + 1 in destination_to_cost):
                if destination_to_cost[B+1] > (B + 1 - point) + cost:
                    heappush(to_delete, destination_to_cost[B+1])
                    destination_to_cost[B+1] = (B + 1 - point) + cost
                    heappush(min_heapq, (B + 1 - point) + cost)
            else:
                destination_to_cost[B+1] = (B + 1 - point) + cost
                heappush(min_heapq, (B + 1 - point) + cost)
                destination.add(B+1)
        destination.pop(point)
        point = destination.upper_bound(point)

    while to_delete and min_heapq[0] == to_delete[0]:
        heappop(min_heapq)
        heappop(to_delete)
    
    if min_heapq:
        print(k + min_heapq[0] + 1)
    else:
        for _ in range(H - k):
            print(-1)
        exit()

Submission status: Runtime Error

Solution code:
from heapq import *


class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
    counter が与えられなかった場合は、全て個数 0 で初期化される。
    閉区間で管理する。
    """

    __slots__ = ["n", "k", "data"]

    def __init__(self, maxvalue, counter = None):
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)
        if counter is not None:
            self.update(counter)
        
    def update(self, counter):
        """
        counter を受け取って、それを反映させる。
        counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
        計算量は、n を要素の最大値として、 O(n) となる。
        """
        if isinstance(counter, list):
            self.data = [0] + counter + [0] * (self.n - len(counter))
        else:
            self.data = [0] * (self.n + 1)
            for k, v in counter.items():
                self.data[k + 1] = v
        for i in range(1, self.n + 1):
            if i + (i & -i) <= self.n:
                self.data[i + (i & -i)] += self.data[i]

    def add(self, value):
        """
        与えられた引数を Multiset に加える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] += 1
            value += value & -value

    def pop(self, value):
        """
        Multiset から与えられた引数を取り除く。
        与えられた引数が Multiset に入っているかのチェックは行わなず、
        単にその個数を 1 減らすだけなので注意。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] -= 1
            value += value & -value

    def count_le(self, value):
        """
        Multiset 内の要素 elem のうち、0 <= elem <= value を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        ret = 0
        while value > 0:
            ret += self.data[value]
            value -= value & -value
        return ret

    def count(self, first, last):
        """
        Multiset 内の要素 elem のうち、first <= elem <= last を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        last += 1
        ret = 0
        while first < last:
            ret += self.data[last]
            last -= last & -last
        while last < first:
            ret -= self.data[first]
            first -= first & -first
        return ret

    def bisect(self, count):
        """
        Multiset 内の要素 elem のうち、count <= count_le(elem) を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        ret = 0
        k = self.k
        while k > 0:
            if ret + k <= self.n and self.data[ret + k] < count:
                count -= self.data[ret + k]
                ret += k
            k //= 2
        return ret


    def lower_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value <= elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value - 1) + 1)

    def upper_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value < elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value) + 1)


H, W = map(int, input().split())

destination = MultisetBIT(W, list(range(W)))

destination_to_cost = {i:0 for i in range(W)}

min_heapq = [0] * W
to_delete = []

for k in range(H):
    # print([i for i in range(W) if destination.count(i, i)])
    # print(destination_to_cost)
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    start_point = destination.lower_bound(A)
    point = start_point
    change_dest_flg = False
    while point < W and point < B + 1:
        change_dest_flg = True
        cost = destination_to_cost.pop(point)
        heappush(to_delete, cost)
        if B + 1 != W:
            if (B + 1 in destination_to_cost):
                if destination_to_cost[B+1] > (B + 1 - point) + cost:
                    heappush(to_delete, destination_to_cost[B+1])
                    destination_to_cost[B+1] = (B + 1 - point) + cost
                    heappush(min_heapq, (B + 1 - point) + cost)
            else:
                destination_to_cost[B+1] = (B + 1 - point) + cost
                heappush(min_heapq, (B + 1 - point) + cost)
                destination.add(B+1)
        destination.pop(point)
        point = destination.upper_bound(point)

    while to_delete and min_heapq[0] == to_delete[0]:
        heappop(min_heapq)
        heappop(to_delete)
    
    if min_heapq:
        print(k + min_heapq[0] + 1)
    else:
        for _ in range(H - k):
            print(-1)
        exit()

Submission status: Runtime Error

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: Runtime Error

Solution code:
import numpy as np

svals = input()
h, w = list(map(int, svals.rstrip(' ').split(' ')))
# print(h,w )

steps = np.zeros([h+1, w], dtype=int)
reach_from_top = np.ones([h+2, w], dtype=bool)
reach_from_left = np.ones([h+1, w+1], dtype=bool)
reach_from_left[:, 0] = 0

for i in range(1, h+1):
    # print('row # {}'.format(i))
    jvals = input()
    j1, j2 = list(map(int, jvals.rstrip(' ').split(' ')))
    # print(j1, j2)
    reach_from_top[i,j1-1:j2] = 0

# print(reach_from_top)


def get_neighbours(i, j):
    n_left = [i, j-1]
    n_up = [i-1, j]
    # print('[{},{}] possible neighbours:{},{}'.format(i, j, n_left, n_up))
    nn = []
    if reach_from_left[i,j] > 0:
        nn.append(n_left)
    if reach_from_top[i,j] > 0:
        nn.append(n_up)
    # print('can reach from:', nn)
    return nn


for row in range(1, h+1):
    # print('row # {}'.format(row))
    for col in range(w):
        nn = get_neighbours(row, col)
        if nn:
            nn_steps = min([steps[ii, jj] for ii, jj in nn])+1
            steps[row, col] = nn_steps
        else:
            reach_from_top[row+1, col] = 0
            reach_from_left[row, col+1] = 0
        # print(steps)
    # print('answer [{}]:'.format(row))
    if steps[row, :].sum() == 0:
        print(-1)
    else:
        print(steps[row, :][steps[row, :] > 0].min())
# print(steps)

Submission status: Runtime Error

Solution code:
import numpy as np

svals = input()
h, w = list(map(int, svals.rstrip(' ').split(' ')))
# print(h,w )

steps = np.zeros([h+1, w],dtype=int)
reach_from_top = np.ones([h+2,w])
reach_from_left = np.ones([h+1, w+1])
reach_from_left[:, 0] = 0

for i in range(1, h+1):
    # print('row # {}'.format(i))
    jvals = input()
    j1, j2 = list(map(int, jvals.rstrip(' ').split(' ')))
    # print(j1, j2)
    reach_from_top[i,j1-1:j2] = 0

# print(reach_from_top)


def get_neighbours(i, j):
    n_left = [i, j-1]
    n_up = [i-1, j]
    # print('[{},{}] possible neighbours:{},{}'.format(i, j, n_left, n_up))
    nn = []
    if reach_from_left[i,j] > 0:
        nn.append(n_left)
    if reach_from_top[i,j] > 0:
        nn.append(n_up)
    # print('can reach from:', nn)
    return nn


for row in range(1, h+1):
    # print('row # {}'.format(row))
    for col in range(w):
        nn = get_neighbours(row, col)
        if nn:
            nn_steps = min([steps[ii, jj] for ii,jj in nn])+1
            steps[row, col] = nn_steps
        else:
            reach_from_top[row+1, col] = 0
            reach_from_left[row, col+1] = 0
        # print(steps)
    # print('answer [{}]:'.format(row))
    if steps[row,:].sum()==0:
        print(-1)
    else:
        print(steps[row,:][steps[row,:]>0].min())
# print(steps)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############


H,N = IL()
raw_data = ILL(H)
# N: 処理する区間の長さ

N0 = 2**(N).bit_length()
data = [None]*(2*N0)
INF = (-1, 2**31-1)
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]
  
update(1,N+1,(0,H))

magarikado = [None for i in range(H)]
for i in range(H)[::-1]:
  update(raw_data[i][0]-1,raw_data[i][1],(H-i,i))
  magarikado[i] = query(raw_data[i][1])
  
#print(magarikado)


best = [2**31-1]*(H+1)
def update2(l,r,v):
  for i in range(l,r):
    best[i] = min(best[i],v)

wall = DD(int)
update2(0,1,0)

for i in range(N):
  nowx = i
  nowy = query(i)
  d = 0
  update2(0,nowy+1,d)
  #print(best)
  if wall[nowy]: continue
  wall[nowy] = 1
  while nowx < N and nowy < H:
    d += raw_data[nowy][1]-nowx
    nowx = raw_data[nowy][1]
    if nowx == N: break
    newy = magarikado[nowy]
    if wall[newy]: break
    wall[newy] = 1
    update2(nowy+1,newy+1,d)
    #print(best)
    nowy = newy
 
    
for i in range(H):
  tmp = best[i+1]
  if tmp == 2**31-1:
    print(-1)
  else:
    print(tmp + i + 1)

Submission status: Runtime Error

Solution code:
#ボツ
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

Q, N = map(int, input().split())
N += 1
INF = 10**12
# N: 処理する区間の長さ
LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [None]*(2*N0)

def gindex(l, r):
	L = (l + N0) >> 1; R = (r + 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(LV):
		if rc <= i:
			yield R
		if L < R and lc <= i:
			yield L
		L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
	for i in reversed(ids):
		v = lazy[i-1]
		if v is None:
			continue
		lazy[2*i-1] = lazy[2*i] = data[2*i-1] = data[2*i] = v >> 1
		lazy[i-1] = None

# 区間[l, r)をxに更新
def update(l, r, x):
	*ids, = gindex(l, r)
	propagates(*ids)

	L = N0 + l; R = N0 + r
	v = x
	while L < R:
		if R & 1:
			R -= 1
			lazy[R-1] = data[R-1] = v
		if L & 1:
			lazy[L-1] = data[L-1] = v
			L += 1
		L >>= 1; R >>= 1; v <<= 1
	for i in ids:
		data[i-1] = data[2*i-1] + data[2*i]

# 区間[l, r)内の合計を求める
def query(l, r):
	propagates(*gindex(l, r))
	L = N0 + l; R = N0 + r

	s = 0
	while L < R:
		if R & 1:
			R -= 1
			s += data[R-1]
		if L & 1:
			s += data[L-1]
			L += 1
		L >>= 1; R >>= 1
	return s

def access(x):
	return query(x, x+1)

lm = 0
update(0, 1, -INF)
update(N, N+1, INF)
for q in range(1, Q+1):
	a, b = map(int, input().split())
	a, b = a-1, b-1
	if a == lm:
		lm = b+1
	update(b+1, b+2, access(b+1) + query(a, b+1) - (b+1-a))
	update(a, b+1, 1)
	res = min(query(0, lm+1), query(0, max(a, 1)), query(0, b+1))
	res += INF
	if res > 10**10:
		print(-1)
	else:
		print(res + q)

Submission status: Runtime Error

Solution code:
#ボツ
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

Q, N = map(int, input().split())
N += 1
INF = 10**12
# N: 処理する区間の長さ
LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [None]*(2*N0)

def gindex(l, r):
	L = (l + N0) >> 1; R = (r + 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(LV):
		if rc <= i:
			yield R
		if L < R and lc <= i:
			yield L
		L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
	for i in reversed(ids):
		v = lazy[i-1]
		if v is None:
			continue
		lazy[2*i-1] = lazy[2*i] = data[2*i-1] = data[2*i] = v >> 1
		lazy[i-1] = None

# 区間[l, r)をxに更新
def update(l, r, x):
	*ids, = gindex(l, r)
	propagates(*ids)

	L = N0 + l; R = N0 + r
	v = x
	while L < R:
		if R & 1:
			R -= 1
			lazy[R-1] = data[R-1] = v
		if L & 1:
			lazy[L-1] = data[L-1] = v
			L += 1
		L >>= 1; R >>= 1; v <<= 1
	for i in ids:
		data[i-1] = data[2*i-1] + data[2*i]

# 区間[l, r)内の合計を求める
def query(l, r):
	propagates(*gindex(l, r))
	L = N0 + l; R = N0 + r

	s = 0
	while L < R:
		if R & 1:
			R -= 1
			s += data[R-1]
		if L & 1:
			s += data[L-1]
			L += 1
		L >>= 1; R >>= 1
	return s

def access(x):
	return query(x, x+1)

lm = 0
update(0, 1, -INF)
update(N, N+1, INF)
for q in range(1, Q+1):
	a, b = map(int, input().split())
	a, b = a-1, b-1
	if a == lm:
		lm = b+1
	update(b+1, b+2, access(b+1) + query(a, b+1) - (b+1-a))
	update(a, b+1, 1)
	res = min(query(0, lm+1), query(0, a), query(0, b+1))
	res += INF
	if res > 10**10:
		print(-1)
	else:
		print(res + q)

Submission status: Runtime Error

Solution code:
class segTree:
  inf = 1e10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, x):
    return s.T[x + s.N - 1]
  def getV(s, l, r):
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))
  def eval(k, l, r):
    if s.L[k] != 0:
      s.T[k] += s.L[k]
      if r - l > 1:
        s.L[2 * k + 1] += s.L[k] / 2
        s.L[2 * k + 2] += s.L[k] / 2
      s.L[k] = 0
  def add(a, b, x, k, l, r):
    if r < 0: r = s.N
    eval(k, l, r)
    if b <= l or r <= a: return
    if a <= l and r <= b:
      s.L[k] += (r - l) * x
      eval(k, l, r)
    else:
      add(a, b, x, 2 * k + 1, l, (l + r) / 2)
      add(a, b, x, 2 * k + 2, (l + r) / 2, r)
      s.T[k] = s.T[2 * k + 1] + s.T[2 * k + 2]

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

L = [0] * W
seg = segTree(W)

inf = 10 ** 18
for i in range(H):
  a, b = AB[i]
  a -= 1
  b -= 1
  if a == 0:
    s = inf
  else:
    s = L[a - 1] + 1
  t = 0
  print(L)
  while a <= b:
    if L[a] == 0:
      seg.update(a, seg.get(a) + s + t)
      s += 1
      a += 1
      L[a] = b + 1
    else:
      # a から min(b, L[a] - 1)にtを足す操作を入れる
      for j in range(a, min(b, L[a] - 1)):
        seg.update(a, seg.get(a) + t)
      a = L[a]
  print(i + 1 + seg.getV(0, W - 1))

for i in seg.T:
  print(i)

Submission status: Runtime Error

Solution code:
from collections import deque

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

q = deque()
q.append([0, 1])
cost = [[-1 for _ in range(W+1)] for _ in range(H+1)]
cost[0][1] = 0

while len(q):
    now = q.popleft()

    h = now[0]
    w = now[1]
    if h != H and cost[h+1][w] == -1 and not (AB[i][0] <= w and w <= AB[i][1]):
        q.append([h+1, w])
        cost[h+1][w] = cost[h][w] + 1
    if w != W and cost[h][w+1] == -1 :
        q.append([h, w+1])
        if h != 0:
            cost[h][w+1] = cost[h][w] + 1
        else:
            cost[h][w+1] = 0

print(cost[H+1][W])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


# ファイル読み込み
def _input():
    lines = open("../tmp_in").readlines()
    for ss in lines:
        yield ss.rstrip()
input = _input().__next__

h,w = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(h)]
dp = [None]*h
v = 1
i = 0
for a,b in ab:
    if a<=v<=b:
        v = b+1
    dp[i] = v
    i += 1
dp2 = [None]*h
done = [0]*h
for i in range(h-1,-1,-1):
    if done[i]:
        continue
    v = w
    l = []
    for j in range(i, -1, -1):
        a,b = ab[j]
        if v==w:
            l.append(j)
        if a<=v<=b:
            v = a-1
    for ind in l:
        dp2[ind] = v
        done[ind] = 1
ans = [None]*h
for i in range(h):
    if dp[i]>w:
        ans[i] = -1
    else:
#         if dp[i]>=dp2[i]:
#             ans[i] = (i+1) + (dp[i]-dp2[i])
#         else:
#             ans[i] = (i+1) + (w-dp2[i])
        ans[i] = min((i+1)+(dp[i]-1), (i+1)+(w-dp2[i]))
write("\n".join(map(str, ans)))

Submission status: Runtime Error

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)]
    y = 1
    t = 0
    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:
                i_max = i
                break

    def C(y):
        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
        if i < i_max:
            return False
        else:
            return True
    l, r = 1, W
    while r - l > 1:
        mid = (r+l)//2
        if C(mid):
            l = mid
        else:
            r = mid
    y = l
    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
    for i in range(H):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
from heapq import *

H, W = map(int, input().split())

destination = list(range(W))
destination_to_cost = {i:0 for i in range(W)}

min_heapq = [0] * W
to_delete = []

for k in range(H):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    start_index = bisect_left(destination, A)
    index = start_index
    change_dest_flg = False
    while index < len(destination) and destination[index] <= B:
        change_dest_flg = True
        cost = destination_to_cost.pop(destination[index])
        heappush(to_delete, cost)
        if B != W - 1:
            if (B + 1 in destination_to_cost):
                if destination_to_cost[B+1] < (B + 1 - destination[index]) + cost:
                    heappush(to_delete, destination_to_cost[B+1])
                    destination_to_cost[B+1] = (B + 1 - destination[index]) + cost
                    heappush(min_heapq, (B + 1 - destination[index]) + cost)
            else:
                destination_to_cost[B+1] = (B + 1 - destination[index]) + cost
                heappush(min_heapq, (B + 1 - destination[index]) + cost)
        index += 1

    while to_delete and min_heapq[0] == to_delete[0]:
        heappop(min_heapq)
        heappop(to_delete)

    if change_dest_flg:
        if B != W - 1:
            destination[start_index:index] = [B + 1]
        else:
            del destination[start_index:index]
        
    
    if min_heapq:
        print(k + min_heapq[0] + 1)
    else:
        for _ in range(H - k):
            print(-1)
        exit()

Submission status: Runtime Error

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 [0,a-1,b+1,W]:
    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])