oj.uz

Submission #526365

# Submission time Handle Problem Language Result Execution time Memory
526365 2022-02-14T13:43:06 Z bebecanvas Exhibition (JOI19_ho_t2) C++14
0 / 100
 12 ms 15180 KB 
#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())+1;
        //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;
	
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Correct 12 ms 15068 KB Output is correct
3 Correct 11 ms 15068 KB Output is correct
4 Correct 11 ms 15060 KB Output is correct
5 Incorrect 11 ms 15180 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Correct 12 ms 15068 KB Output is correct
3 Correct 11 ms 15068 KB Output is correct
4 Correct 11 ms 15060 KB Output is correct
5 Incorrect 11 ms 15180 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Correct 12 ms 15068 KB Output is correct
3 Correct 11 ms 15068 KB Output is correct
4 Correct 11 ms 15060 KB Output is correct
5 Incorrect 11 ms 15180 KB Output isn't correct
6 Halted 0 ms 0 KB -