結果

問題 No.2501 Maximum Inversion Number
コンテスト
ユーザー titia
提出日時 2023-10-15 02:07:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,759 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 124,496 KB
最終ジャッジ日時 2024-09-16 19:39:28
合計ジャッジ時間 5,252 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 13
権限があれば一括ダウンロードができます

ソースコード

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