結果
問題 |
No.728 ギブ and テイク
|
ユーザー |
![]() |
提出日時 | 2025-07-30 03:20:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,503 ms / 3,000 ms |
コード長 | 1,231 bytes |
コンパイル時間 | 375 ms |
コンパイル使用メモリ | 82,880 KB |
実行使用メモリ | 359,684 KB |
最終ジャッジ日時 | 2025-07-30 03:21:14 |
合計ジャッジ時間 | 21,100 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import sys import io, os input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline from operator import itemgetter N=int(input()) A=list(map(int,input().split())) LR=[list(map(int,input().split())) for i in range(N)] S=[] Q=[] for i in range(N): a=A[i] l=A[i]-LR[i][0] r=A[i]+LR[i][1] S.append(a) S.append(l) S.append(r) Q.append((a,0,l)) Q.append((r,1,a)) S=sorted(set(S)) D={S[i]:i+2 for i in range(len(S))} LEN=len(S)+5 BIT=[0]*(LEN+1) # 1-indexedなtree. 配列BITの長さはLEN+1にしていることに注意。 def update(v,w): # index vにwを加える while v<=LEN: BIT[v]+=w v+=(v&(-v)) # v&(-v)で、最も下の立っているビット. 自分を含む大きなノードへ. たとえばv=3→v=4 def getvalue(v): # [1,v]の区間の和を求める ANS=0 while v!=0: ANS+=BIT[v] v-=(v&(-v)) # 自分より小さい自分の和を構成するノードへ. たとえばv=14→v=12へ return ANS Q.sort(key=itemgetter(1)) Q.sort(key=itemgetter(0)) ANS=0 for a,com,l in Q: if com==0: d=D[a] le=D[l] ANS+=getvalue(d)-getvalue(le-1) update(d,1) else: update(D[l],-1) print(ANS)