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: Wrong Answer

Solution code:
class segTree:
  inf = 1e18
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [0] * (2 * s.N)
    s.L = [0] * (2 * s.N)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i + 1, 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):
    s.propagates(*s.getIndex(x, x + 1))
    return s.T[x + s.N - 1]
  def getV(s, l, r):
    s.propagates(*s.getIndex(l, r))
    L = l + s.N
    R = r + s.N
    p = s.inf
    while L < R:
      if R & 1:
        R -= 1
        p = s.do(p, s.T[R - 1])
      if L & 1:
        p = s.do(p, s.T[L - 1])
        L += 1
      L >>= 1
      R >>= 1
    return p
  def getIndex(s, l, r):
    L = l + s.N
    R = r + s.N
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
      if R <= rm:
        yield R
      if L <= lm:
        yield L
      L >>= 1
      R >>= 1
    while L:
      yield L
      L >>= 1
  def propagates(s, *ids):
    for i in reversed(ids):
      v = s.L[i - 1]
      if not v: continue
      s.L[2 * i - 1] += v
      s.L[2 * i] += v
      s.T[2 * i - 1] += v
      s.T[2 * i] += v
      s.L[i - 1] = 0
  def addArea(s, l, r, x):
    L = s.N + l
    R = s.N + r
    while L < R:
      if R & 1:
        R -= 1
        s.L[R - 1] += x
        s.T[R - 1] += x
      if L & 1:
        s.L[L - 1] += x
        s.T[L - 1] += x
        L += 1
      L >>= 1
      R >>= 1
    for i in s.getIndex(l, r):
      s.T[i - 1] = s.do(s.T[2 * i - 1], s.T[2 * i]) + s.L[i - 1]
  def updateArea(s, l, r, x):
    *ids, = s.getIndex(l, r)
    s.propagates(*ids)
    L = s.N + l
    R = s.N + r
    while L < R:
      if R & 1:
        R -= 1
        s.L[R - 1] = s.T[R - 1] = x
      if L & 1:
        s.L[L - 1] = s.T[L - 1] = x
        L += 1
      L >>= 1
      R >>= 1
    for i in ids:
      s.T[i - 1] = s.do(s.T[2 * i - 1], s.T[2 * i])

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

seg = segTree(W)
segL = 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 = seg.get(a - 1) + 1
  while a <= b:
    toa = segL.get(a)
    if toa == 0:
      seg.update(a, seg.get(a) + min(inf, s))
      segL.update(a, b + 1)
      s += 1
      a += 1
    else:
      t = s - seg.get(a)
      seg.addArea(a, min(b + 1, toa), min(inf, t))
      segL.updateArea(a, min(b + 1, toa), b + 1)
      a = toa
      if a > b: break
      s = seg.get(a - 1)

  ans = seg.getV(0, W) + i + 1
  if ans >= inf:
    print(-1)
  else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd, sqrt, cos, radians, pi, floor, ceil
from collections import defaultdict as d
from itertools import combinations as c
from string import ascii_lowercase as a

h, w = map(int, input().split())
f = 0
grid = []
for i in range(h):
	a, b = map(int, input().split())
	grid += [[a, b]]
grid += [[0, 0]]
start = 0
for i in range(w):
	if (i + 1) < grid[0][0] or (i + 1) > grid[0][1]:
		start = i + 1
		break
if not start:
	f = 1

step = 0
black = 0
for i in range(1, h + 1):
	if f:
		print(-1)
	else:
		if not black:
			if start >= grid[i][0] and start <= grid[i][1]:
				black = 1
			step += 1
		else:
			if grid[i-1][1] == w:
				f = 1
				step = -1
			else:
				step += (grid[i-1][1] - start) + 1
				start = grid[i-1][1] + 1
				if start >= grid[i][0] and start <= grid[i][1]:
					black = 1
				step += 1
		print(step)

Submission status: Wrong Answer

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

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

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

#min_list = [INF] * (H+3)
#MAP = defaultdict(lambda : INF)

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

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

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

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

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


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

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

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


def run():
    bfs()

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from typing import List
from heapq import heappush, heappop, heapify
import sys
from collections import defaultdict
INF = 10**6
def main(H, W, AB):
    cur = list(range(W))
    cur_f = BinaryIndexedTree(initial_values=[1] * W)
    rt = RemovableHeapq([0] * W)
    for i, (a, b) in enumerate(AB):
        a -= 1
        mr = -1
        while True:
            j = cur_f.bisect(lambda x: x <= cur_f.query(a - 1))
            if j >= W or j > b: break
            mr = cur[j]
            cur_f.add(j, -1)
            rt.remove(j - cur[j])
        if mr >= 0 and b < W:
            cur_f.add(b, 1)
            cur[b] = mr
            rt.push(b - mr)
        ans = -1
        if not rt.is_empty():
            ans = rt.pop_min() + i + 1
        print(ans)

class RemovableHeapq:
    def __init__(self, l: List[int]):
        heapify(l)
        d = defaultdict(int)
        for e in l:
            d[e] += 1
        self.h, self.d = l, d

    def push(self, item: int):
        heappush(self.h, item)
        self.d[item] += 1

    def remove(self, item: int):
        d = self.d
        if d[item] > 0:
            d[item] -= 1

    def pop_min(self) -> int:
        h, d = self.h, self.d
        while True:
            m = heappop(h)
            if d[m] >= 1:
                return m

    def is_empty(self) -> bool:
        h, d = self.h, self.d
        while h:
            if d[h[0]] == 0:
                heappop(h)
            else:
                break
        return len(h) == 0

class BinaryIndexedTree:
    def __init__(self, n=None, f=lambda x, y: x + y, identity=0, initial_values=None):
        assert(n or initial_values)
        self.__f, self.__id, = f, identity
        self.__n = len(initial_values) if initial_values else n
        self.__d = [identity] * (self.__n + 1)
        if initial_values:
            for i, v in enumerate(initial_values): self.add(i, v)

    def add(self, i, v):
        n, f, d = self.__n, self.__f, self.__d
        i += 1
        while i <= n:
            d[i] = f(d[i], v)
            i += -i & i

    def query(self, r):
        res, f, d = self.__id, self.__f, self.__d
        r += 1
        while r:
            res = f(res, d[r])
            r -= -r & r
        return res

    def bisect(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        n, f, d, v = self.__n, self.__f, self.__d, self.__id
        x, i = 0, 1 << (n.bit_length() - 1)
        while i > 0:
            if x + i <= n and func(f(v, d[x + i])): v, x = f(v, d[x + i]), x + i
            i >>= 1
        return x

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(H)]
    main(H, W, AB)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())

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

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
from itertools import accumulate
import bisect

import sys
input = sys.stdin.readline
import math as mt


def solve(h,w):
    dp = {}
    for j in range(w):
        dp[j] = 0
    for i in range(h):
        a,b = list(map(int,input().split()))
        a -=  1
        b -=  1
        if b == h-1:
            b = 10**8
        tmp = -1 
        dellist = []
        for j in dp:
            if a <= dp[j]+j <= b:
                dp[j] = b+1-j
                if j < tmp:
                   dellist.append(j) 
                else:
                    if tmp >= 0:
                        dellist.append(tmp)
                    tmp = j
        for j in dellist:
            del dp[j]
        #print(dp)
        ans = min(dp.values())+i+1
        if ans > 10**7:
            print(-1)
        else:
            print(ans)





            

def main():
    h,w = list(map(int,input().split()))
    solve(h,w)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
from itertools import accumulate
import bisect

import sys
input = sys.stdin.readline
import math as mt

MAXN = 10**6 +1
  
# stores smallest prime factor for 
# every number 
spf = [0 for i in range(MAXN)] 
  
# Calculating SPF (Smallest Prime Factor)  
# for every number till MAXN. 
# Time Complexity : O(nloglogn) 

def solve(h,w):
    dp = {}
    for j in range(w):
        dp[j] = 0
    for i in range(h):
        a,b = list(map(int,input().split()))
        a -=  1
        b -=  1
        flag = False
        if b == h-1:
            b = 10**8
        for j in dp:
            if a <= dp[j]+j <= b:
                dp[j] = b+1-j
        tmp = -1 
        dellist = []
        for j in dp:
            if dp[j] == b+1-j:
                if j < tmp:
                   dellist.append(j) 
                else:
                    if tmp >= 0:
                        dellist.append(tmp)
                    tmp = j
        for j in dellist:
            del dp[j]
        #print(dp)
        ans = min(dp.values())+i+1
        if ans > 10**7:
            print(-1)
        else:
            print(ans)





            

def main():
    h,w = list(map(int,input().split()))
    solve(h,w)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class LazySegTree:
        # Range update query
        def __init__(self, A, initialize=True, segfunc=min, ident=2 ** 31 - 1):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)
            self.lazy = [0] * (self.N0 * 2)
            self.lazy_flg = [False] * (self.N0 * 2)

        def _ascend(self, i):
            for _ in range(i.bit_length() - 1):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

        def _descend(self, idx):
            lv = idx.bit_length()
            block_size = 2**self.LV
            for j in range(lv - 1, 0, -1):
                i = idx >> j
                block_size >>= 1
                x = self.lazy[i]
                if not self.lazy_flg[i]:
                    continue
                self.lazy_flg[i] = False
                self.lazy[i * 2] = x
                self.lazy[i * 2 + 1] = x + block_size
                self.lazy_flg[i * 2] = True
                self.lazy_flg[i * 2 + 1] = True
                self.data[i * 2] = x
                self.data[i * 2 + 1] = x + block_size

        # open interval [l, r)
        def update(self, l, r, x):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            l_ori = l
            r_ori = r
            xl = x
            xr = x + (r-l)
            block_size = 1
            while l < r:
                if l & 1:
                    self.data[l] = xl
                    self.lazy[l] = xl
                    self.lazy_flg[l] = True
                    l += 1
                    xl += block_size
                if r & 1:
                    r -= 1
                    self.data[r] = xr - block_size
                    self.lazy[r] = xr - block_size
                    self.lazy_flg[r] = True
                    xr -= block_size
                l >>= 1
                r >>= 1
                block_size >>= 1
            self._ascend(l_ori // (l_ori & -l_ori))
            self._ascend(r_ori // (r_ori & -r_ori) - 1)

        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            ret = self.ident
            while l < r:
                if l & 1:
                    ret = self.segfunc(ret, self.data[l])
                    l += 1
                if r & 1:
                    ret = self.segfunc(self.data[r - 1], ret)
                    r -= 1
                l >>= 1
                r >>= 1
            return ret

    H, W = map(int, input().split())
    ST = LazySegTree([10**6] + [0] * W)
    for h in range(H):
        a, b = map(int, input().split())
        ST.update(a+1, b+2, ST.query(a, a+1)+1)
        ans = ST.query(2, W+2)
        if ans >= 10**6:
            print(-1)
        else:
            print(h + 1 + ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import *


class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    閉区間で管理する。
    """

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

    def __init__(self, maxvalue):
        "内部では [1, maxvalue + 1] でもつ。"
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)

    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 >>= 1
        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)
for i in range(W):
    destination.add(i)

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_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 != W - 1:
            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: Wrong Answer

Solution code:
from heapq import *


class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    閉区間で管理する。
    """

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

    def __init__(self, maxvalue):
        "内部では [1, maxvalue + 1] でもつ。"
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)

    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 >>= 1
        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)
for i in range(W):
    destination.add(i)

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_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 != W - 1:
            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: Wrong Answer

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
H,W=reads()
minpos=[0 for i in range(H+1)]
for i in range(1,H+1):
    a,b=reads()
    a-=1
    if a<=minpos[i-1]:
        minpos[i]=max(minpos[i-1],b)
    else:
        minpos[i]=minpos[i-1]
    if(minpos[i]==W):
      print(-1)
    else:
      print(i+minpos[i])

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
H,W=reads()
minpos=[0 for i in range(H+1)]
for i in range(1,H+1):
    a,b=reads()
    a-=1
    if a<=minpos[i-1]:
        minpos[i]=b
    else:
        minpos[i]=minpos[i-1]
    if(minpos[i]==W):
      print(-1)
    else:
      print(i+minpos[i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h,w=map(int, input().split())

class segtree:
    x_unit=1<<30 # 単位元
    x_func=min  # 関数
    def __init__(self,n):
        self.n=n
        self.x=[self.x_unit]*(2*n)
    def build(self, seq):
        for i,j in enumerate(seq, self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func(self.x[i*2], self.x[i*2+1])
    def set_val(self,i,j): # 1点更新
        origin=i+0
        i += self.n
        if j>self.x[i]:
            self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            if origin<=self.x[i] and self.x[i]<j:
                self.x[i]=j
            elif self.x[i]<self.x[i*2]:
                self.x[i]=self.x[i*2]
    def fold(self,l,r): # 区間[l, r)を取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func(val_l,self.x[l])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func(val_r,self.x[r])
            l //= 2
            r //= 2
        return self.x_func(val_l,val_r)

seg=segtree(w)
seq=[i for i in range(w)]
seg.build(seq)
#print(seg.x)
for i in range(h):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if b+1<w:
        seg.set_val(a, b+1)
        seg.set_val(b, b+1)
    else:
        seg.set_val(a, 1<<30)
        seg.set_val(b, 1<<30)
    #print(seg.x)
    if seg.x[1]==1<<30:
        print(-1)
    else:
        print(seg.x[1]+(i+1))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h,w=map(int, input().split())

class segtree:
    x_unit=1<<30 # 単位元
    x_func=min  # 関数
    def __init__(self,n):
        self.n=n
        self.x=[self.x_unit]*(2*n)
    def build(self, seq):
        for i,j in enumerate(seq, self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func(self.x[i*2], self.x[i*2+1])
    def set_val(self,i,j): # 1点更新
        origin=i+0
        i += self.n
        if j>self.x[i]:
            self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            if origin<=self.x[i] and self.x[i]<j:
                self.x[i]=j
            else:
                self.x[i]=self.x[i*2]
    def fold(self,l,r,x): # 区間[l, r)をxに更新 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func(val_l,self.x[l])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func(val_r,self.x[r])
            l //= 2
            r //= 2
        return self.x_func(val_l,val_r)

seg=segtree(w)
seq=[i for i in range(w)]
seg.build(seq)
#print(seg.x)
for i in range(h):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if b+1<w:
        seg.set_val(a, b+1)
        seg.set_val(b, b+1)
    else:
        seg.set_val(a, 1<<30)
        seg.set_val(b, 1<<30)
    #print(seg.x)
    if seg.x[1]==1<<30:
        print(-1)
    else:
        print(seg.x[1]+(i+1))