提出 #6462886


ソースコード 拡げる

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))

提出情報

提出日時
問題 E - Sequence Decomposing
ユーザ shakayami
言語 PyPy3 (2.4.0)
得点 500
コード長 1145 Byte
結果 AC
実行時間 873 ms
メモリ 66896 KB

ジャッジ結果

セット名 All Sample
得点 / 配点 500 / 500 0 / 0
結果
AC × 35
AC × 2
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
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