結果

問題 No.1703 Much Matching
ユーザー ooaiu
提出日時 2025-09-15 07:44:30
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 770 bytes
コンパイル時間 4,435 ms
コンパイル使用メモリ 173,524 KB
実行使用メモリ 11,024 KB
最終ジャッジ日時 2025-09-15 07:44:46
合計ジャッジ時間 9,135 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::static_modint<(int)1e9+7>;
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, m, q;
	cin >> n >> m >> q;
	vector<pair<int,int>> p(q);
	for(int i = 0; i < q; i++) cin >> p[i].first >> p[i].second;
	sort(p.begin(), p.end());
	vector<int> dp(m + 1, 1e9);
	dp[0] = 0;
	for(int i = 0; i < q; ) {
		int j = i;
		while(j < q && p[i].first == p[j].first) j++;
		vector<pair<int,int>>lz;
		for(int k = i; k < j; k++) {
			int id = lower_bound(dp.begin(),dp.end(),p[k].second)-dp.begin();
			lz.push_back({id,p[k].second});
		}
		for(auto[id,v]:lz)dp[id]=v;
		i = j;
	}
	int ans=0;
	for(int i = 0; i <= m; i++) if(dp[i]!=1e9)ans=i;
	cout<<ans<<"\n";
}
0