結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2022-03-08 15:25:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 269 ms / 2,000 ms |
コード長 | 1,714 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 82,156 KB |
実行使用メモリ | 116,920 KB |
最終ジャッジ日時 | 2024-07-23 15:18:57 |
合計ジャッジ時間 | 4,579 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
class BIT:def __init__(self, n):self.n = nself.bit = [0]*(self.n+1) # 1-indexeddef init(self, init_val):for i, v in enumerate(init_val):self.add(i, v)def add(self, i, x):# i: 0-indexedi += 1 # to 1-indexedwhile i <= self.n:self.bit[i] += xi += (i & -i)def sum(self, i, j):# return sum of [i, j)# i, j: 0-indexedreturn self._sum(j) - self._sum(i)def _sum(self, i):# return sum of [0, i)# i: 0-indexedres = 0while i > 0:res += self.bit[i]i -= i & (-i)return resdef lower_bound(self, x):s = 0pos = 0depth = self.n.bit_length()v = 1 << depthfor i in range(depth, -1, -1):k = pos + vif k <= self.n and s + self.bit[k] < x:s += self.bit[k]pos += vv >>= 1return posdef __str__(self): # for debugarr = [self.sum(i,i+1) for i in range(self.n)]return str(arr)import sysimport io, osinput = io.BytesIO(os.read(0,os.fstat(0).st_size)).readlinefrom itertools import accumulaten, m = map(int, input().split())Q = [[] for i in range(m)]CR = [0]*(m+1)bit = BIT(m+1)L = []for i in range(n):l, r = map(int, input().split())if l > r:l, r = r, lQ[r].append(l)bit.add(l, 1)L.append(l)CR[r+1] += 1ans = n*(n-1)//2CR = list(accumulate(CR))for l in L:ans -= CR[l]Q = [sorted(x) for x in Q]for r in range(m):for l in Q[r]:ans -= bit.sum(0, l)bit.add(l, -1)print(ans)