結果

問題 No.1708 Quality of Contest
コンテスト
ユーザー fujisyo32
提出日時 2021-10-26 14:10:45
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 2,219 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 86,588 KB
最終ジャッジ日時 2024-10-05 09:18:06
合計ジャッジ時間 11,098 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 RE * 4 TLE * 2 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

N,M,X=map(int, input().split())

A=[]
B=[]
for i in range(N):
   a,b=map(int, input().split())
   A.append(a)
   B.append(b)
K=int(input())
C=list(map(int, input().split()))
AB=list(zip(A,B))
AB=sorted(AB,key=lambda x:-x[0])

D=[[] for _ in range(M)]
for i in range(N):
    D[AB[i][1]-1].append(AB[i][0])

D_now = [0 for _ in range(M)]
E = []
for i in range(M):
    if len(D[i])!=0:
        E.append(-D[i][0]*1e10-i)

heapq.heapify(E)
used=set()
ANS=[]

while(len(E)!=0):
    e1_ = heapq.heappop(E)
    e1 = (-(int)((-e1_)//1e10),(int)((-e1_)%1e10))
    F=[]
    e2=(1e10,-1)
    e2_=0
    #print(e1)
    if e1[1] not in used:
        ANS.append((-e1[0],e1[1]))
        if e1[1]<0 or e1[1]>=M:
            print("break",e1)
        elif len(D[e1[1]])>D_now[e1[1]]+1:
            heapq.heappush(E, (-D[e1[1]][D_now[e1[1]]+1]*1e10-e1[1]))
            D_now[e1[1]]+=1
        used.add(e1[1])

    else:
        while(len(E)!=0):
            e_ = heapq.heappop(E)
            e=(-(int)((-e_)//1e10),(int)((-e_)%1e10))
            if e[1] not in used:
                e2= e
                e2_=e_
                break
            else:
                F.append(e_)
            if len(E)==0:
                break

        if e1[0]<e2[0]-X or e2[1]==-1:
            ANS.append((-e1[0],e1[1]))
            used.add(e1[1])
            if len(D[e1[1]])>D_now[e1[1]]+1:
                heapq.heappush(E, (-D[e1[1]][D_now[e1[1]]+1]*1e10-e1[1]))
                D_now[e1[1]]+=1
            if e2[0]!=1e10:
                F.append(e2_)
        else:
            ANS.append((-e2[0],e2[1]))
            used.add(e2[1])
            if e2[1]<0 or e2[1]>=M:
                print("break",e2)
            elif len(D[e2[1]])>D_now[e2[1]]+1:
                heapq.heappush(E, (-D[e2[1]][D_now[e2[1]]+1]*1e10-e2[1]))
                D_now[e2[1]]+=1
            F.append(e1_)
            
    for f in F:
        heapq.heappush(E, f)
        

#print(ANS)
ANS2=[0]
used2=set()
now=0
for i in range(N):
    if ANS[i][1] not in used2:
        used2.add(ANS[i][1])
        now+=X+ANS[i][0]
        ANS2.append(now)
    else:
        now+=ANS[i][0]
        ANS2.append(now)

ans=0
for k in range(K):
    ans+=ANS2[C[k]]
print(ans)
0