結果

問題 No.1703 Much Matching
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:27:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,328 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 214,760 KB
最終ジャッジ日時 2025-04-15 21:31:21
合計ジャッジ時間 7,546 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    Q = int(input[idx]); idx +=1

    pairs = defaultdict(list)
    for _ in range(Q):
        a = int(input[idx]); idx +=1
        b = int(input[idx]); idx +=1
        pairs[a].append(b)
    
    # Sort the x's and for each x, sort the y's in descending order
    sorted_xs = sorted(pairs.keys())
    for x in sorted_xs:
        pairs[x].sort(reverse=True)
    
    dp = []
    for x in sorted_xs:
        ys = pairs[x]
        max_new_len = 0
        best_y = None
        for y in ys:
            # Find the largest index where dp[index] < y
            pos = bisect.bisect_left(dp, y) - 1
            new_len = pos + 1
            if new_len + 1 > max_new_len:
                max_new_len = new_len + 1
                best_y = y
            elif new_len + 1 == max_new_len:
                if best_y is None or y < best_y:
                    best_y = y
        if best_y is not None:
            if max_new_len > len(dp):
                dp.append(best_y)
            else:
                if best_y < dp[max_new_len - 1]:
                    dp[max_new_len - 1] = best_y
    print(len(dp))

if __name__ == "__main__":
    main()
0