結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2020-03-20 03:07:49 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 828 ms / 2,000 ms |
コード長 | 1,582 bytes |
コンパイル時間 | 144 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 35,652 KB |
最終ジャッジ日時 | 2024-12-14 03:52:18 |
合計ジャッジ時間 | 10,594 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#!/usr/bin/ python3.8import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesclass BinaryIndexedTree():def __init__(self, seq):self.size = len(seq)self.depth = self.size.bit_length()self.build(seq)def build(self, seq):data = seqsize = self.sizefor i, x in enumerate(data):j = i + (i & (-i))if j < size:data[j] += data[i]self.data = datadef __repr__(self):return self.data.__repr__()def get_sum(self, i):data = self.datas = 0while i:s += data[i]i -= i & -ireturn sdef add(self, i, x):data = self.datasize = self.sizewhile i < size:data[i] += xi += i & -idef find_kth_element(self, k):data = self.data; size = self.sizex, sx = 0, 0dx = 1 << (self.depth)for i in range(self.depth - 1, -1, -1):dx = (1 << i)if x + dx >= size:continuey = x + dxsy = sx + data[y]if sy < k:x, sx = y, syreturn x + 1N, M = map(int, readline().split())m = map(int, read().split())LR = []for L, R in zip(m, m):if L > R:L, R = R, LLR.append((L + 1, R + 1))LR.sort()bit = BinaryIndexedTree([0] * (M + 10))answer = 0for L, R in LR:answer += bit.get_sum(R) - bit.get_sum(L)bit.add(R, 1)print(answer)