Contest Duration: - (local time) (100 minutes) Back to Home

Submission #6462886

Source Code Expand

Copy
```class BITree:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)

def total(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s

while i <= self.size:
self.tree[i] += x
i += i & -i
N=int(input())
A=[int(input())*(10**5)-i for i in range(N)]
#追加削除
#二分検索
B=[0]+sorted(list(set([i for i in A])))
M=len(B)
D=dict()
for i in range(M):
D[B[i]]=i
#print(B)
S=BITree(M)
def search(X):
Y=D[X]
tmp=S.total(Y)
if tmp!=S.total(Y-1):
return Y
left=0
right=Y-1
mid=(left+right)//2
while(left<=right):
mid=(left+right)//2
if S.total(mid)<tmp:
left=mid+1
else:
right=mid-1
return left
for i in range(N):
#print([S.total(i+1)-S.total(i) for i in range(M)])
#print([S.total(i) for i in range(M+1)])
tmp2=search(A[i])
if tmp2==0:
else:
print(S.total(M))```

#### Submission Info

Submission Time 2019-07-20 21:36:35+0900 E - Sequence Decomposing shakayami PyPy3 (2.4.0) 500 1145 Byte AC 873 ms 66896 KB

#### Judge Result

Set Name All Sample
Score / Max Score 500 / 500 0 / 0
Status
 AC × 35
 AC × 2
Set Name Test Cases
All all_same, killer_01, killer_02, killer_03, killer_04, killer_05, many_dup_01, many_dup_02, many_dup_03, many_dup_04, many_dup_05, many_dup_06, many_dup_07, many_dup_08, many_dup_09, many_dup_10, many_dup_11, many_dup_12, rand_max_01, rand_max_02, rand_max_03, rand_max_04, rand_max_05, rand_max_06, rand_max_07, rand_max_08, rand_max_09, rand_max_10, rand_max_11, sample_01, sample_02, sorted_ascending, sorted_descending, unique_perm_01, unique_perm_02
Sample sample_01, sample_02
Case Name Status Exec Time Memory
all_same AC 733 ms 66128 KB
killer_01 AC 749 ms 66768 KB
killer_02 AC 721 ms 66512 KB
killer_03 AC 756 ms 66640 KB
killer_04 AC 795 ms 66640 KB
killer_05 AC 803 ms 66768 KB
many_dup_01 AC 808 ms 66640 KB
many_dup_02 AC 821 ms 66640 KB
many_dup_03 AC 799 ms 66512 KB
many_dup_04 AC 819 ms 66768 KB
many_dup_05 AC 848 ms 66896 KB
many_dup_06 AC 792 ms 66384 KB
many_dup_07 AC 802 ms 66768 KB
many_dup_08 AC 824 ms 66768 KB
many_dup_09 AC 740 ms 64720 KB
many_dup_10 AC 787 ms 66512 KB
many_dup_11 AC 821 ms 66640 KB
many_dup_12 AC 761 ms 64592 KB
rand_max_01 AC 873 ms 66640 KB
rand_max_02 AC 821 ms 66512 KB
rand_max_03 AC 795 ms 64720 KB
rand_max_04 AC 812 ms 66512 KB
rand_max_05 AC 830 ms 64720 KB
rand_max_06 AC 814 ms 66384 KB
rand_max_07 AC 824 ms 66512 KB
rand_max_08 AC 844 ms 66512 KB
rand_max_09 AC 812 ms 64720 KB
rand_max_10 AC 860 ms 66640 KB
rand_max_11 AC 862 ms 66384 KB
sample_01 AC 176 ms 38256 KB
sample_02 AC 174 ms 38256 KB
sorted_ascending AC 760 ms 66384 KB
sorted_descending AC 739 ms 66256 KB
unique_perm_01 AC 808 ms 66256 KB
unique_perm_02 AC 849 ms 66256 KB