Submission #1188581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188581		ofoz	Bouquet (EGOI24_bouquet)	Pypy 3	70 / 100	3097 ms	225804 KiB

Main

from math import ceil


def update(v: int, tl: int, tr: int, i: int, tree: list, segments: list, dp: list):
    if tl == tr:
        tree[v] = [tl, tl, dp[tl]]
    else:
        tm = (tl+tr)//2
        if i <= tm:
            update(2*v, tl, tm, i, tree, segments, dp)
        else:
            update(2*v+1, tm+1, tr, i, tree, segments, dp)
        
        tree[v] = [
            min(tree[2*v][0], tree[2*v+1][0]),
            max(tree[2*v][1], tree[2*v+1][1]),
            max(tree[2*v][2], tree[2*v+1][2])
        ]

def query(v: int, tl: int, tr: int, x: int, tree: list):
    # print(tl, tr, tree[v], x)
    if x <= tree[v][0]: return 0
    if x > tree[v][1]: return tree[v][2]
    
    tm = (tl+tr)//2
    a = query(2*v, tl, tm, x, tree)
    b = query(2*v+1, tm+1, tr, x, tree)
    return max(a, b)




def solve():
    n = int(input())
    tree = [[float('inf'), float('inf'), -1] for _ in range(4*n)] 
    dp = [1] * n
    segments = []
    for i in range(n):
        l, r = map(int, input().split(" "))
        segments.append((l, r))
    
    upd = [[] for _ in range(n)]
    for i in range(n):
        # print(tree)
        l, r = segments[i]
        mx_j = query(1, 0, n-1, i - l, tree)
        dp[i] = max(dp[i], mx_j + 1)
        upd[min(n-1, i + r)].append(i)
        for j in upd[i]:
            update(1, 0, n-1, j, tree, segments, dp)

    # print(query(1, 0, n-1, n-1, tree))
    print(max(dp))

# j < i - l[i]

solve()

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 47%)

=======

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 0 / 30