Submission #2559566
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
Submission Time | |
---|---|
Task | B - リス |
User | yaketake08 |
Language | PyPy3 (2.4.0) |
Score | 1 |
Code Size | 720 Byte |
Status | AC |
Exec Time | 674 ms |
Memory | 120004 KB |
Judge Result
Set Name | sample | all | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1 / 1 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt |
all | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 163 ms | 38384 KB |
01-02.txt | AC | 167 ms | 38256 KB |
01-03.txt | AC | 162 ms | 38256 KB |
01-04.txt | AC | 161 ms | 38256 KB |
01-05.txt | AC | 162 ms | 38256 KB |
01-06.txt | AC | 197 ms | 40944 KB |
01-07.txt | AC | 202 ms | 42224 KB |
01-08.txt | AC | 196 ms | 41968 KB |
01-09.txt | AC | 226 ms | 45532 KB |
01-10.txt | AC | 673 ms | 118520 KB |
01-11.txt | AC | 668 ms | 118392 KB |
01-12.txt | AC | 674 ms | 118392 KB |
01-13.txt | AC | 641 ms | 119244 KB |
01-14.txt | AC | 645 ms | 119244 KB |
01-15.txt | AC | 636 ms | 119492 KB |
01-16.txt | AC | 633 ms | 119492 KB |
01-17.txt | AC | 515 ms | 97076 KB |
01-18.txt | AC | 538 ms | 120004 KB |
sample-01.txt | AC | 161 ms | 38256 KB |
sample-02.txt | AC | 163 ms | 38256 KB |
sample-03.txt | AC | 161 ms | 38256 KB |