제출 #526368

#제출 시각아이디문제언어결과실행 시간메모리
526368bebecanvasExhibition (JOI19_ho_t2)C++14
0 / 100
15 ms15180 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define sz(x) (int) (x).size() struct node{ int s, m, e; int val; node *l, *r; node(int S, int E){ s= S, e= E, m=(s+e)/2; val=0; if(s!=e){ l= new node(s,m); r= new node(m+1, e); } } void update(int X, int V){ if(s==e){val= V;} else{ if(X<=m){l->update(X,V);} else{r->update(X,V);} val= max(l->val, r->val); } } int query(int S, int E){ if(s==S && e==E){return val;} else if(E<=m){return l->query(S,E);} else if(S>= m+1){return r->query(S,E);} else{return max(l->query(S,m),r->query(m+1, E));} } } *root; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; pair<int, int> p[100005]; for(int i=0; i<n; i++){ int a, b; cin >> a >> b; p[i]= make_pair(a, b); } int f[100005]; for(int i=0; i<m; i++){cin >> f[i];} sort(p, p+n); sort(f, f+m); priority_queue<int> pq; vector<int> ans; int l= 0; for(int i=0; i<m; i++){ //cout << i << endl; while(p[l].first<=f[i]&&l<n){ pq.push(-1*p[l].second); l++; } if(!pq.empty()){ int minn= pq.top(); pq.pop(); minn*= -1; ans.push_back(minn); } } //cout << "LOL" << endl; root= new node(0, 100005); vector<int> dis; int size= sz(ans); for(int i = 0;i < size;i++) dis.push_back(ans[i]); sort(dis.begin(), dis.end()); dis.erase(unique(dis.begin(), dis.end()), dis.end()); for(int i = 0;i < size;i++){ ans[i]=(lower_bound(dis.begin(),dis.end(),ans[i]) - dis.begin()); //cout << b << endl; } int dp[100005]; int anss= 0; for(int i=0; i<size; i++){ dp[i]= root->query(0, ans[i]) +1; //cout << dp[i] << endl; root->update(ans[i], dp[i]); anss= max(anss, dp[i]); } cout << anss << endl; } /* 8 8 508917604 35617051 501958939 840246141 485338402 32896484 957730250 357542366 904165504 137209882 684085683 775621730 552953629 20004459 125090903 607302990 433255278 979756183 28423637 856448848 276518245 314201319 666094038 149542543 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...