結果
問題 |
No.743 Segments on a Polygon
|
ユーザー |
![]() |
提出日時 | 2025-03-31 18:00:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 452 ms / 2,000 ms |
コード長 | 1,521 bytes |
コンパイル時間 | 261 ms |
コンパイル使用メモリ | 82,820 KB |
実行使用メモリ | 109,368 KB |
最終ジャッジ日時 | 2025-03-31 18:01:07 |
合計ジャッジ時間 | 5,587 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
import sys from bisect import bisect_left class FenwickTree: def __init__(self, size): self.size = size self.tree = [0] * (size + 2) def update(self, idx, delta=1): idx += 1 while idx <= self.size + 1: self.tree[idx] += delta idx += idx & -idx def query(self, idx): idx += 1 res = 0 while idx > 0: res += self.tree[idx] idx -= idx & -idx return res def main(): input = sys.stdin.read().split() ptr = 0 N, M = int(input[ptr]), int(input[ptr+1]) ptr +=2 chords = [] for _ in range(N): a, b = int(input[ptr]), int(input[ptr+1]) ptr +=2 if a > b: a, b = b, a chords.append((a, b)) # Sort the chords based on their s_i (start) chords.sort() ft = FenwickTree(M) total = 0 for s, e in chords: if s < e: # Forward chord, query (s, e) upper = e -1 count = ft.query(upper) - ft.query(s) total += count else: # Backward chord (s >= e), split into (s, M-1) and [0, e-1] # Part1: (s, M-1] part1 = ft.query(M-1) - ft.query(s) # Part2: [0, e-1] part2 = 0 if e > 0: part2 = ft.query(e-1) total += part1 + part2 # Add e to Fenwick tree. Ensure e is in [0, M-1] ft.update(e) print(total) if __name__ == "__main__": main()