結果
問題 |
No.743 Segments on a Polygon
|
ユーザー |
![]() |
提出日時 | 2025-09-24 08:44:07 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 848 bytes |
コンパイル時間 | 586 ms |
コンパイル使用メモリ | 82,664 KB |
実行使用メモリ | 89,156 KB |
最終ジャッジ日時 | 2025-09-24 08:44:13 |
合計ジャッジ時間 | 6,092 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | RE * 10 |
ソースコード
import sys input = sys.stdin.readline N,M=map(int,input().split()) A=[list(map(int,input().split())) for i in range(N)] for i in range(N): if A[i][0]>A[i][1]: A[i][0],A[i][1]=A[i][1],A[i][0] LEN=N+10 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 A.sort() ANS=0 for a,b in A: ANS+=getvalue(b+1)-getvalue(a+1) update(b+1,1) print(ANS)