oj.uz

Submission #702638

# Submission time Handle Problem Language Result Execution time Memory
702638 2023-02-24T16:33:11 Z ihceker Exhibition (JOI19_ho_t2) C++14
0 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

const int N=100000;
int s[(N+5)*4];

void update(int node,int l,int r,int x,int y){
	if(l>x || r<x || l>r)return;
    if(l==r){
        s[node]=max(s[node],y);
        return;
    }
    int mid=(l+r)/2;
    update(node*2,l,mid,x,y);
    update(node*2+1,mid+1,r,x,y);
    s[node]=max(s[node*2],s[node*2+1]);
    return;
}

int query(int node,int l,int r,int x,int y){
	if(l>y || r<x || l>r)return INT_MIN;
	if(l>=x && r<=y)return s[node];
	int mid=(l+r)/2;
	return max(query(node*2,l,mid,x,y),query(node*2+1,mid+1,r,x,y));
}

int32_t main(){
	fast;
	int n,m;
	cin>>n>>m;
	vector<int>v;
	pair<int,int>a[n];
	set<int>st;
	for(int i=0;i<n;i++){
	    int x,y;
	    cin>>x>>y;
	    a[i]={y,x};
	    st.insert(x);
	    v.pb(x);
	}
	map<int,int>mp,mp2;
	int cnt=1;
	for(auto i:st){
	    mp[i]=cnt++;
	}
	for(int i=0;i<n;i++){
		a[i].ss=mp[a[i].ss];
	}
	int b[m];
	for(int i=0;i<m;i++){
	    cin>>b[i];
	}
	sort(b,b+m);
	reverse(b,b+m);
	sort(all(v));
	reverse(all(v));
	int ind=0;
	sort(a,a+n);
	reverse(a,a+n);
	for(auto i:v){
	    while(ind<m && b[ind]>=i){
	        ind++;
	    }
	    mp2[mp[i]]=ind;
	}
	int mx=0;
	for(int i=0;i<n;i++){
	    int x=min(mp2[a[i].ss],query(1,1,N,a[i].ss,N)+1);
	    mx=max(mx,x);
	    update(1,1,N,a[i].ss,x);
	}
	cout<<mx<<endl;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 50.0

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