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:
      dic[i] = {}
      min_count = inf
      while dic[i - 1]:
        j, value = dic[i - 1].popitem()
        if a <= j and j <= b:
          if b != w:
            count = value + b - j + 2
            k = b + 1
          else:
            count = inf
            k = w + 1
        else:
          count = value + 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:
import sys,heapq
input = sys.stdin.buffer.readline


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

    #dp[i] : iの時の最小右移動回数
    dp = [0]*(w+1)

    #解候補
    res = [0]*w

    #解候補から消されるもの
    anti = []


    #Ai = {1:dp[i]はvalid 0:invalid}

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(w+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= w:
            BIT[idx] += x
            idx += idx&(-idx)

    for i in range(1,w+1):
        BIT_update(i,1)

    for i in range(1,h+1):
        a,b = map(int,input().split())
        
        #a-1,b+1の値を計算
        x = a-1
        if x != 0 and x != w+1 and dp[x] == -1:
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = x
                ng = 0
                while ok-ng > 1:
                    mid = (ok+ng)//2
                    if BIT_query(mid) == k:
                        ok = mid
                    else:
                        ng = mid
                #xをvalidにする
                dp[x] = dp[ok] + (x-ok)
                BIT_update(x,1)
                heapq.heappush(res,dp[x])
                
        x = b+1
        if x != 0 and x != w+1 and dp[x] == -1:
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = x
                ng = 0
                while ok-ng > 1:
                    mid = (ok+ng)//2
                    if BIT_query(mid) == k:
                        ok = mid
                    else:
                        ng = mid
                #xをvalidにする
                dp[x] = dp[ok] + (x-ok)
                BIT_update(x,1)
                heapq.heappush(res,dp[x])

        k = BIT_query(a-1)+1

        while True:
            ng = a-1
            ok = w
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) >= k:
                    ok = mid
                else:
                    ng = mid

            if ok > b or dp[ok] == -1:
                break
            
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            BIT_update(ok,-1)
        
        while anti and res and anti[0] == res[0]:
            heapq.heappop(anti)
            heapq.heappop(res)

        if res:
            print(res[0]+i)
        else:
            print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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

    #dp[i] : iの時の最小右移動回数
    dp = [0]*(w+1)

    #解候補
    res = [0]*w

    #解候補から消されるもの
    anti = []


    #Ai = {1:dp[i]はvalid 0:invalid}

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(w+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= w:
            BIT[idx] += x
            idx += idx&(-idx)

    for i in range(1,w+1):
        BIT_update(i,1)

    for i in range(1,h+1):
        a,b = map(int,input().split())
        
        #a-1,b+1の値を計算
        for x in [a-1,b+1]:
            #端で操作不可能
            if x in (0,w+1):
                continue

            #validな値の場合そのまま下に行く
            if dp[x] != -1:
                continue
            
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k == 0:
                continue
            ok = x
            ng = 0
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) == k:
                    ok = mid
                else:
                    ng = mid
            #xをvalidにする
            dp[x] = dp[ok] + (x-ok)
            BIT_update(x,1)
            heapq.heappush(res,dp[x])

        k = BIT_query(a-1)+1

        while True:
            ng = a-1
            ok = w
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) >= k:
                    ok = mid
                else:
                    ng = mid

            if ok > b or dp[ok] == -1:
                break
            
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            BIT_update(ok,-1)
        
        while anti and res and anti[0] == res[0]:
            heapq.heappop(anti)
            heapq.heappop(res)

        if res:
            print(res[0]+i)
        else:
            print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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


    #dp[i] : iの時の最小右移動回数
    dp = [0]*(w+1)


    #解候補
    res = [0]*w

    #解候補から消されるもの
    anti = []



    #Ai = {1:dp[i]はvalid 0:invalid}

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(w+100)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= w:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,w+1):
        BIT_update(i,1)


    for i in range(1,h+1):
        a,b = map(int,input().split())
        
        #a-1,b+1の値を計算
        for x in [a-1,b+1]:
            #端で操作不可能
            if x in (0,w+1):
                continue

            #validな値の場合そのまま下に行く
            if dp[x] != -1:
                continue
            
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k == 0:
                continue
            ok = x
            ng = 0
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) == k:
                    ok = mid
                else:
                    ng = mid
            #xをvalidにする
            dp[x] = dp[ok] + (x-ok)
            BIT_update(x,1)
            heapq.heappush(res,dp[x])

        k = BIT_query(a-1)+1

        while True:
            ng = a-1
            ok = w
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) >= k:
                    ok = mid
                else:
                    ng = mid

            if ok > b:
                break
            
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            BIT_update(ok,-1)
        
        while anti and anti[0] == res[0]:
            heapq.heappop(anti)
            heapq.heappop(res)

        if res:
            print(res[0]+i)
        else:
            print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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


    #dp[i] : iの時の最小右移動回数
    dp = [0]*(w+1)


    #解候補
    res = [0]*w

    #解候補から消されるもの
    anti = []



    #Ai = {1:dp[i]はvalid 0:invalid}

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(w+100)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= w:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,w+1):
        BIT_update(i,1)


    for i in range(1,h+1):
        a,b = map(int,input().split())
        
        #a-1,b+1の値を計算
        for x in [a-1,b+1]:
            #端で操作不可能
            if x in (0,w+1):
                continue

            #validな値の場合そのまま下に行く
            if dp[x] != -1:
                continue
            
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k == 0:
                continue
            ok = x
            ng = 0
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) == k:
                    ok = mid
                else:
                    ng = mid
            #xをvalidにする
            dp[x] = dp[ok] + (x-ok)
            BIT_update(x,1)
            heapq.heappush(res,dp[x])

        k = BIT_query(a-1)+1

        while True:
            ng = a-1
            ok = w
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) >= k:
                    ok = mid
                else:
                    ng = mid

            if ok > b or dp[ok] == -1:
                break
            
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            BIT_update(ok,-1)
        
        while anti and res and anti[0] == res[0]:
            heapq.heappop(anti)
            heapq.heappop(res)

        if res:
            print(res[0]+i)
        else:
            print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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


    #dp[i] : iの時の最小右移動回数
    dp = [0]*(w+1)


    #解候補
    res = [0]*w

    #解候補から消されるもの
    anti = []



    #Ai = {1:dp[i]はvalid 0:invalid}

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(w+100)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= w:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,w+1):
        BIT_update(i,1)


    for i in range(1,h+1):
        a,b = map(int,input().split())
        
        #a-1,b+1の値を計算
        for x in [a-1,b+1]:
            #端で操作不可能
            if x in (0,w+1):
                continue

            #validな値の場合そのまま下に行く
            if dp[x] != -1:
                continue
            
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k == 0:
                continue
            ok = x
            ng = 0
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) == k:
                    ok = mid
                else:
                    ng = mid
            #xをvalidにする
            dp[x] = dp[ok] + (x-ok)
            BIT_update(x,1)
            heapq.heappush(res,dp[x])

        k = BIT_query(a-1)+1

        while True:
            ng = 0
            ok = w
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) >= k:
                    ok = mid
                else:
                    ng = mid

            if ok > b or dp[ok] == -1:
                break
            
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            BIT_update(ok,-1)
        
        while anti and res and anti[0] == res[0]:
            heapq.heappop(anti)
            heapq.heappop(res)

        if res:
            print(res[0]+i)
        else:
            print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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


#dp[i] : iの時の最小右移動回数
dp = [0]*(w+1)


#解候補
res = [0]*w

#解候補から消されるもの
anti = []



#Ai = {1:dp[i]はvalid 0:invalid}

#A1 ... AnのBIT(1-indexed)
BIT = [0]*(w+100)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= w:
        BIT[idx] += x
        idx += idx&(-idx)
    return

for i in range(1,w+1):
    BIT_update(i,1)


for i in range(1,h+1):
    a,b = map(int,input().split())
    
    #a-1,b+1の値を計算
    for x in [a-1,b+1]:
        #端で操作不可能
        if x in (0,w+1):
            continue

        #validな値の場合そのまま下に行く
        if dp[x] != -1:
            continue
        
        #x以下のvalidな個数
        k = BIT_query(x-1)

        #k番目のvalidな位置okからXに行く
        if k == 0:
            continue
        ok = x
        ng = 0
        while ok-ng > 1:
            mid = (ok+ng)//2
            if BIT_query(mid) == k:
                ok = mid
            else:
                ng = mid
        #xをvalidにする
        dp[x] = dp[ok] + (x-ok)
        BIT_update(x,1)
        heapq.heappush(res,dp[x])

    k = BIT_query(a-1)+1

    while True:
        ng = 0
        ok = w
        while ok-ng > 1:
            mid = (ok+ng)//2
            if BIT_query(mid) >= k:
                ok = mid
            else:
                ng = mid

        if ok > b or dp[ok] == -1:
            break
        
        heapq.heappush(anti,dp[ok])
        dp[ok] = -1
        BIT_update(ok,-1)
    
    while anti and res and anti[0] == res[0]:
        heapq.heappop(anti)
        heapq.heappop(res)

    if res:
        print(res[0]+i)
    else:
        print(-1)

Submission status: Time Limit Exceeded

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

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


#dp[i] : iの時の最小右移動回数
dp = [0]*(w+1)
dp[0] = -1

#解候補
res = [0]*w

#解候補から消されるもの
anti = []



#Ai = {1:dp[i]はvalid 0:invalid}

#A1 ... AnのBIT(1-indexed)
BIT = [0]*(w+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= w:
        BIT[idx] += x
        idx += idx&(-idx)
    return

for i in range(1,w+1):
    BIT_update(i,1)


for i in range(1,h+1):
    a,b = map(int,input().split())
    
    #a-1,b+1の値を計算
    for x in [a-1,b+1]:
        #端で操作不可能
        if x in (0,w+1):
            continue

        #validな値の場合そのまま下に行く
        if dp[x] != -1:
            continue
        
        #x以下のvalidな個数
        k = BIT_query(x-1)

        #k番目のvalidな位置okからXに行く
        if k == 0:
            continue
        ok = x
        ng = 0
        while ok-ng > 1:
            mid = (ok+ng)//2
            if BIT_query(mid) == k:
                ok = mid
            else:
                ng = mid
        #xをvalidにする
        dp[x] = dp[ok] + (x-ok)
        BIT_update(x,1)
        heapq.heappush(res,dp[x])

    k = BIT_query(a-1)+1

    while True:
        ng = 0
        ok = w
        while ok-ng > 1:
            mid = (ok+ng)//2
            if BIT_query(mid) >= k:
                ok = mid
            else:
                ng = mid

        if ok > b or dp[ok] == -1:
            break
        
        heapq.heappush(anti,dp[ok])
        dp[ok] = -1
        BIT_update(ok,-1)
    
    while anti and anti[0] == res[0]:
        heapq.heappop(anti)
        heapq.heappop(res)

    if res:
        print(res[0]+i)
    else:
        print(-1)

Submission status: Time Limit Exceeded

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

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


#dp[i] : iの時の最小右移動回数
dp = [0]*(w+1)

#解候補
res = [0]*w

#解候補から消されるもの
anti = []



#Ai = {1:dp[i]はvalid 0:invalid}

#A1 ... AnのBIT(1-indexed)
BIT = [0]*(w+100)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= w:
        BIT[idx] += x
        idx += idx&(-idx)
    return

for i in range(1,w+1):
    BIT_update(i,1)
flag = False

for i in range(1,h+1):
    a,b = map(int,input().split())
    if flag:
        print(-1)
        continue
    #a-1,b+1の値を計算
    for x in [a-1,b+1]:
        #端で操作不可能
        if x in (0,w+1):
            continue

        #validな値の場合そのまま下に行く
        if dp[x] != -1:
            continue
        
        #x以下のvalidな個数
        k = BIT_query(x-1)

        #k番目のvalidな位置okからXに行く
        if k == 0:
            continue
        ok = x
        ng = 0
        while ok-ng > 1:
            mid = (ok+ng)//2
            if BIT_query(mid) == k:
                ok = mid
            else:
                ng = mid
        #xをvalidにする
        dp[x] = dp[ok] + (x-ok)
        BIT_update(x,1)
        heapq.heappush(res,dp[x])

    k = BIT_query(a-1)+1

    while True:
        ng = 0
        ok = w
        while ok-ng > 1:
            mid = (ok+ng)//2
            if BIT_query(mid) >= k:
                ok = mid
            else:
                ng = mid

        if ok > b or dp[ok] == -1:
            break
        
        heapq.heappush(anti,dp[ok])
        dp[ok] = -1
        BIT_update(ok,-1)
    
    while anti and anti[0] == res[0]:
        heapq.heappop(anti)
        heapq.heappop(res)

    if res:
        print(res[0]+i)
    else:
        flag = True
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
#"""
H, W = [int(n) for n in input().split(" ")]
A = []
B = []
for _ in range(H):
    a, b = [int(n) for n in input().split(" ")]
    A.append(a - 1)
    B.append(b - 1)
#"""
"""
H = 4000
W = 4000
A = []
B = []
import random
for _ in range(H):
    a = random.randint(1, W)
    b = random.randint(1, W)
    if a > b:
        a, b = b, a
    A.append(a - 1)
    B.append(b - 1)
"""

INF = 10000000

X = [[n, n, -1] for n in range(W)]
#print(X)
for k in range(H):
    for a in X:
        start = a[1]
        end = start
        if start >= A[k] and start <= B[k]:
            if B[k] >= W - 1:
                end = INF
            else:
                end = B[k] + 1
        a[2] = end
    #print(X)
    scores = []
    for a in X:
        score = a[2] - a[0] + k + 1
        scores.append(score)
    if len(scores) <= 0:
        print("-1")
    else:
        minscore = min(scores)
        if minscore >= INF:
            minscore = -1
        print(minscore)
    #print(X)
    X = sorted(X, key=lambda x:(x[1], x[0]), reverse=True)
    nextX = []
    lastEnd = INF + 1
    for a in X:
        if a[2] != INF and a[2] != lastEnd:
            nextX.append([a[0], a[2], -1])
            lastEnd = a[2]
    X = nextX
    #print(X)
    k += 1

"""
5 4
2 4
1 1
2 3
2 4
1 4
"""

Submission status: Time Limit Exceeded

Solution code:
#"""
H, W = [int(n) for n in input().split(" ")]
A = []
B = []
for _ in range(H):
    a, b = [int(n) for n in input().split(" ")]
    A.append(a - 1)
    B.append(b - 1)
#"""
"""
H = 4000
W = 4000
A = []
B = []
import random
for _ in range(H):
    a = random.randint(1, W)
    b = random.randint(1, W)
    if a > b:
        a, b = b, a
    A.append(a - 1)
    B.append(b - 1)
"""

INF = 10000000

X = [[n, n, -1] for n in range(W)]
#print(X)
for k in range(H):
    for a in X:
        start = a[1]
        end = start
        if start >= A[k] and start <= B[k]:
            if B[k] >= W - 1:
                end = INF
            else:
                end = B[k] + 1
        a[2] = end
    #print(X)
    scores = []
    for a in X:
        score = a[2] - a[0] + k + 1
        scores.append(score)
    if len(scores) <= 0:
        print("-1")
    else:
        minscore = min(scores)
        if minscore >= INF:
            minscore = -1
        print(minscore)
    nextX = []
    for a in X:
        if a[2] != INF:
            nextX.append([a[0], a[2], -1])
    X = nextX
    k += 1

"""
5 4
2 4
1 1
2 3
2 4
1 4
"""

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

A = np.zeros(W, dtype='int64')
inf = 10 ** 9
flag = False
for i, (a, b) in enumerate(Prohibit):
    A += 1
    a -= 1
    if a > 0:
        A[a:b] = np.arange(A[a-1] + 1, A[a-1] + 1 + b - a)
    if a == 0:
        A[a:b] = inf
    if min(A) >= inf:
        flag = True
    if flag:
        print(-1)
    else:
        print(min(A))