Submission #526368

#	Time	Username	Problem	Language	Result	Execution time	Memory
526368		bebecanvas	Exhibition (JOI19_ho_t2)	C++14	0 / 100	15 ms	15180 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);
		}
	}
	
	//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
*/

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