結果

問題 No.1703 Much Matching
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:07:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 972 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 154,436 KB
最終ジャッジ日時 2025-06-12 18:09:22
合計ジャッジ時間 25,282 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32 TLE * 2 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 1)  # 1-based indexing

    def update(self, idx, value):
        while idx <= self.n:
            if self.tree[idx] < value:
                self.tree[idx] = value
            else:
                break  # No need to proceed if current value is not larger
            idx += idx & -idx

    def query(self, idx):
        res = 0
        while idx > 0:
            if self.tree[idx] > res:
                res = self.tree[idx]
            idx -= idx & -idx
        return res

n, m, q = map(int, input().split())
pairs = [tuple(map(int, input().split())) for _ in range(q)]
pairs.sort(key=lambda x: (x[0], -x[1]))  # Sort by a_i ascending, then b_i descending

ft = FenwickTree(m)
max_len = 0

for a, b in pairs:
    prev_max = ft.query(b - 1)
    current = prev_max + 1
    ft.update(b, current)
    if current > max_len:
        max_len = current

print(max_len)
0