結果
問題 | 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;}