結果

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

ソースコード

diff # 

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

    def update(self, idx, value):
        if idx > self.n:
            return
        if self.data[idx] >= value:
            return
        self.data[idx] = value
        while idx <= self.n:
            if self.tree[idx] < value:
                self.tree[idx] = value
            else:
                break
            idx += idx & -idx

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

    def get(self, idx):
        return self.data[idx]

n, m, q = map(int, input().split())
pairs = []
for _ in range(q):
    a, b = map(int, input().split())
    pairs.append((a, b))

# Sort pairs by a (ascending), then by b (ascending)
pairs.sort(key=lambda x: (x[0], x[1]))

ft = FenwickTreeMax(m)
max_ans = 0

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

print(max_ans)
0