結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2021-03-21 18:12:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 507 ms / 2,000 ms |
コード長 | 1,553 bytes |
コンパイル時間 | 391 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 87,512 KB |
最終ジャッジ日時 | 2024-11-22 12:17:47 |
合計ジャッジ時間 | 7,489 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
class segment_tree:__slots__ = ["op_M", "e_M","N","N0","dat"]def __init__(self, N, operator_M, e_M):self.op_M = operator_Mself.e_M = e_Mself.N = Nself.N0 = 1<<(N-1).bit_length()self.dat = [self.e_M]*(2*self.N0)# 長さNの配列 initial で初期化def build(self, initial):assert self.N == len(initial)self.dat[self.N0:self.N0+len(initial)] = initial[:]for k in range(self.N0-1,0,-1):self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])# a_k の値を x に更新def update(self,k,x):k += self.N0self.dat[k] = xk >>= 1while k:self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])k >>= 1# 区間[L,R]をopでまとめるdef query(self,L,R):L += self.N0; R += self.N0 + 1sl = sr = self.e_Mwhile L < R:if R & 1:R -= 1sr = self.op_M(self.dat[R],sr)if L & 1:sl = self.op_M(sl,self.dat[L])L += 1L >>= 1; R >>= 1return self.op_M(sl,sr)def get(self, k): #k番目の値を取得。query[k,k]と同じreturn self.dat[k+self.N0]n,m = map(int,input().split())ab = []for _ in range(n):a,b = sorted(map(int,input().split()))ab.append((a,b))ab.sort()ans = 0from operator import addseg = segment_tree(m,add,0)for a,b in ab:x = seg.query(a,b)ans += xseg.update(b,1)print(ans)