Submission #6476416


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
 
    def add(self, i, x):
        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:
        S.add(D[A[i]],1)
    else:
        S.add(D[A[i]],1)
        S.add(tmp2,-1)
print(S.total(M))

Submission Info

Submission Time
Task E - Sequence Decomposing
User shakayami
Language Python (3.4.3)
Score 0
Code Size 1147 Byte
Status TLE
Exec Time 2105 ms
Memory 25208 KB

Judge Result

Set Name All Sample
Score / Max Score 0 / 500 0 / 0
Status
AC × 2
TLE × 33
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 TLE 2104 ms 23136 KB
killer_01 TLE 2104 ms 23040 KB
killer_02 TLE 2104 ms 22564 KB
killer_03 TLE 2104 ms 23032 KB
killer_04 TLE 2104 ms 22908 KB
killer_05 TLE 2104 ms 25068 KB
many_dup_01 TLE 2104 ms 22788 KB
many_dup_02 TLE 2104 ms 22912 KB
many_dup_03 TLE 2104 ms 22688 KB
many_dup_04 TLE 2104 ms 25088 KB
many_dup_05 TLE 2105 ms 23144 KB
many_dup_06 TLE 2104 ms 22564 KB
many_dup_07 TLE 2105 ms 23148 KB
many_dup_08 TLE 2104 ms 23148 KB
many_dup_09 TLE 2104 ms 24508 KB
many_dup_10 TLE 2105 ms 23024 KB
many_dup_11 TLE 2105 ms 23144 KB
many_dup_12 TLE 2105 ms 22448 KB
rand_max_01 TLE 2104 ms 24844 KB
rand_max_02 TLE 2105 ms 22556 KB
rand_max_03 TLE 2105 ms 22340 KB
rand_max_04 TLE 2105 ms 22556 KB
rand_max_05 TLE 2104 ms 24516 KB
rand_max_06 TLE 2105 ms 22564 KB
rand_max_07 TLE 2105 ms 22676 KB
rand_max_08 TLE 2104 ms 22688 KB
rand_max_09 TLE 2104 ms 22456 KB
rand_max_10 TLE 2104 ms 25208 KB
rand_max_11 TLE 2105 ms 22572 KB
sample_01 AC 17 ms 3064 KB
sample_02 AC 17 ms 3064 KB
sorted_ascending TLE 2105 ms 22824 KB
sorted_descending TLE 2105 ms 22796 KB
unique_perm_01 TLE 2104 ms 22676 KB
unique_perm_02 TLE 2105 ms 22672 KB