Submission #2559563

---

Source Code Expand

from bisect import bisect
N = int(input())
*A, = map(int, input().split())
N0 = 2**(N-1).bit_length()

data = [i & -i for i in range(N+1)]
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def lower_bound(x):
    w = i = 0
    k = N0
    while k:
        if i+k <= N and w + data[i+k] <= x:
            w += data[i+k]
            i += k
        k >>= 1
    return i+1

B = [None]*N
for i in range(N-1, -1, -1):
    x = lower_bound(i-A[i])
    B[x-1] = i+1
    add(x, -1)

INF = 10**9
C = [INF]*(N+1)
C[0] = 0
for b in B:
    C[bisect(C, b)] = b
print(bisect(C, INF-1)-1)

Submission Info

Judge Result