oj.uz

Submission #526369

# Submission time Handle Problem Language Result Execution time Memory
526369 2022-02-14T13:50:14 Z bebecanvas Exhibition (JOI19_ho_t2) C++14
0 / 100
 3 ms 3404 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);
		}
	}
	
	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.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 50.0

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