結果
問題 | No.1703 Much Matching |
ユーザー |
![]() |
提出日時 | 2025-03-31 17:18:50 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,515 bytes |
コンパイル時間 | 157 ms |
コンパイル使用メモリ | 82,596 KB |
実行使用メモリ | 182,352 KB |
最終ジャッジ日時 | 2025-03-31 17:19:52 |
合計ジャッジ時間 | 25,260 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 WA * 25 TLE * 2 -- * 1 |
ソースコード
class FenwickTreeMax: def __init__(self, size): self.size = size self.tree = [0] * (size + 2) # 1-based indexing, size up to M (10^3) def update(self, index, value): while index <= self.size: if self.tree[index] < value: self.tree[index] = value else: break # No need to update further if the value is not larger index += index & -index def query(self, index): res = 0 while index > 0: res = max(res, self.tree[index]) index -= index & -index return res def main(): import sys input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]); ptr +=1 M = int(input[ptr]); ptr +=1 Q = int(input[ptr]); ptr +=1 pairs = [] for _ in range(Q): a = int(input[ptr]); ptr +=1 b = int(input[ptr]); ptr +=1 pairs.append( (a, b) ) # Sort by x, then y pairs.sort(key=lambda x: (x[0], x[1])) ft = FenwickTreeMax(M) max_answer = 0 for (x, y) in pairs: # Query max up to y-1 if y == 1: max_prev = 0 else: max_prev = ft.query(y-1) current = max_prev +1 # Check current max at y current_val = ft.query(y) # Current maximum up to y if current_val < current: ft.update(y, current) if current > max_answer: max_answer = current print(max_answer) if __name__ == "__main__": main()