結果
問題 |
No.728 ギブ and テイク
|
ユーザー |
![]() |
提出日時 | 2025-07-30 03:17:57 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,108 bytes |
コンパイル時間 | 481 ms |
コンパイル使用メモリ | 82,900 KB |
実行使用メモリ | 360,860 KB |
最終ジャッジ日時 | 2025-07-30 03:18:23 |
合計ジャッジ時間 | 26,127 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 TLE * 1 |
ソースコード
import sys input = sys.stdin.readline 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() 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)