結果

問題 No.2501 Maximum Inversion Number
ユーザー titiatitia
提出日時 2023-10-15 02:07:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,759 bytes
コンパイル時間 439 ms
コンパイル使用メモリ 87,104 KB
実行使用メモリ 125,788 KB
最終ジャッジ日時 2023-10-15 02:07:28
合計ジャッジ時間 6,284 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 68 ms
71,024 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 165 ms
109,716 KB
testcase_09 AC 114 ms
91,936 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 489 ms
82,904 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

def tentou(A):
    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)

    return ANS

T=int(input())
for tests in range(T):
    n,m=map(int,input().split())
    L=list(map(int,input().split()))
    R=list(map(int,input().split()))

    if sum(L)<=m<=sum(R):
        pass
    else:
        print(-1)
        continue

    OK=0
    NG=10**9+1

    while OK+1<NG:
        mid=(OK+NG)//2

        count=0
        for i in range(n):
            count+=min(mid,R[i])

        if count<=m:
            OK=mid
        else:
            NG=mid

    #print(OK)

    rest=m
    KO=[0]*n
    CAN=[]

    for i in range(n):
        x=min(OK,R[i])
        KO[i]=x
        rest-=x

        if x<R[i]:
            CAN.append(i)

    for j in range(rest):
        KO[CAN[j]]+=1

    #print(KO)

    SUM=0
    ANS=0
    for ko in KO:
        ANS+=SUM*ko
        SUM+=ko

    print(ANS)
0