Submission #526369

#	Time	Username	Problem	Language	Result	Execution time	Memory
526369		bebecanvas	Exhibition (JOI19_ho_t2)	C++14	0 / 100	3 ms	3404 KiB

joi2019_ho_t2

#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);
		}
	}
	
	int dp[100005];
	for(int i=0; i<m; i++){dp[i]=0;}
	
	int anss=0;
	int size= sz(ans);
	for(int i=0; i<size; i++){
		int maxVal=0;
		for(int j=0; j<i; j++){
			if(ans[i]>=ans[j]){
				maxVal= max(maxVal, dp[j]);
			}
		}
		dp[i]= maxVal + 1;
		anss= max(dp[i], anss);
	}

	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
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50