結果

問題 No.694 square1001 and Permutation 3
ユーザー titiatitia
提出日時 2024-11-07 07:01:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,020 bytes
コンパイル時間 380 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 123,008 KB
最終ジャッジ日時 2024-11-07 07:01:25
合計ジャッジ時間 5,522 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 RE -
testcase_06 RE -
testcase_07 WA -
testcase_08 WA -
testcase_09 RE -
testcase_10 WA -
testcase_11 RE -
testcase_12 RE -
testcase_13 AC 41 ms
52,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

N=int(input())
A=[int(input()) for i in range(N)]

LEN=len(A)
MAX=max(A)
MIN=min(A)

BIT=[0]*(MAX-MIN+2) # 出現回数をbit indexed treeの形でもっておく.

def update(v,w): # index vにwを加える
    while v<=MAX-MIN+1:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # MIN～vの区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # たとえばv=3→v=2へ
    return ANS

ANS=0        
for i in range(LEN): # A[0],A[1],...とBITを更新しながら,各A[i]について転倒数を求める.
    bit_ai=A[i]-MIN+1 # A[i]がBITの中で何番目か

    ANS+=i # 今まで出現した個数.
    ANS-=getvalue(bit_ai) # 今まで出現した中で,MIN～bit_aiの個数を減らす.
    # bit_ai～MAXの出現個数が転倒数

    update(bit_ai,1)

#print(ANS)
LANS=[ANS]

for a in A:
    plus=N-a
    minus=a-1

    LANS.append(LANS[-1]+plus-minus)

LANS.pop()
print("\n".join(map(str,LANS)))
0