Submission #427775

#TimeUsernameProblemLanguageResultExecution timeMemory
427775ChaskaExhibition (JOI19_ho_t2)C++11
0 / 100
1 ms420 KiB
#include <bits/stdc++.h> #define F first #define S second using namespace std; typedef pair<int,int> i2; const int N = 3e5+5; int n,m,b[N]; i2 ax[N]; int cnt,res,x,st[4*N],a[N]; set<int> s; map<int,int> h; void get(int no,int in,int fin,int val) { if (fin < val) return; if(val <= in) { x = max(x,st[no]); return; } int mid = (in+fin)/2; get(no*2+1,in,mid,val); get(no*2+2,mid+1,fin,val); return; } void upd(int no,int in,int fin,int pos) { if (fin < pos || in > pos) return; if (in == fin) { st[no] = max(st[no],x); return; } int mid = (in+fin)/2; upd(no*2+1,in,mid,pos); upd(no*2+2,mid+1,fin,pos); st[no] = max(st[no*2+1],st[no*2+2]); return; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); cin >> n >> m; for (int i=0;i<n;i++) cin >> ax[i].S >> ax[i].F; for (int i=0;i<m;i++) cin >> b[i]; sort(ax,ax+n); for (int i=0;i<n;i++){ a[i] = ax[i].S; s.insert(a[i]); } for (int i=0;i<m;i++){s.insert(b[i]);} for (int u : s) h[u] = ++cnt; for (int i=0;i<n;i++) a[i] = h[a[i]]; for (int i=0;i<m;i++) b[i] = h[b[i]]; sort(b,b+m); // for (int i=0;i<n;i++) cout<< a[i ] << " "; for (int i=n-1;i>=0;i--) { x = 0; get(0,1,cnt,a[i]); x++; if (x>m) { x=m; upd(0,1,cnt,a[i]); //cout << x << " "; } else { int p = b[m-x]; if (a[i] > p) { x--; upd(0,1,cnt,a[i]); } else { upd(0,1,cnt,a[i]); } // cout << x << " "; } } cout << st[0]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...