結果
問題 | No.1703 Much Matching |
ユーザー |
![]() |
提出日時 | 2021-10-08 22:13:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 733 ms / 2,000 ms |
コード長 | 1,304 bytes |
コンパイル時間 | 2,598 ms |
コンパイル使用メモリ | 210,436 KB |
最終ジャッジ日時 | 2025-01-24 22:20:51 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; int inf = 1001001001; template <typename T> struct SegmentTree { int n; vector<T> dat; SegmentTree() {} SegmentTree(int N) { n = 1; while(n < N) { n *= 2; } dat.resize(2*n-1,-inf); } void update(int x, T val) { x += (n-1); dat[x] = val; while(x > 0) { x = (x-1)/2; dat[x] = max(dat[2*x+1],dat[2*x+2]); } } T query(int a, int b, int k, int l, int r) { if(r <= a || b <= l) return -inf; if(a <= l && r <= b) return dat[k]; T vl = query(a, b, 2*k+1, l, (l+r)/2); T vr = query(a, b, 2*k+2, (l+r)/2, r); return max(vl, vr); } T query(int a,int b) {//[a,b) return query(a,b,0,0,n); } }; int main() { int N,M,Q; cin >> N >> M >> Q; map<int,vector<int>>tmp; for(int i = 0; i < Q; i++) { int a,b; cin >> a >> b; tmp[a].push_back(b); } SegmentTree<int>Seg(M+1); Seg.update(0,0); for(auto x:tmp) { sort(x.second.rbegin(),x.second.rend()); for(int i = 0; i < x.second.size(); i++) { Seg.update(x.second[i],Seg.query(0,x.second[i])+1); } } cout << Seg.query(0,M+1) << endl; }