Submission #704049

#	Time	Username	Problem	Language	Result	Execution time	Memory
704049		1075508020060209tc	Exhibition (JOI19_ho_t2)	C++14	100 / 100	131 ms	5588 KiB

joi2019_ho_t2

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int m;
pair<int,int>paint[500005];
int buc[500005];

int ok(int mi){
int it=m-mi+1;
for(int i=1;i<=n;i++){
    if(buc[it]>=paint[i].second){
        it++;
        if(it==m+1){return 1;}
    }
}
return 0;
}


signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>paint[i].second>>paint[i].first;
}
sort(paint+1,paint+n+1);
for(int i=1;i<=m;i++){
    cin>>buc[i];
}
sort(buc+1,buc+m+1);

int l=0;int r=m;
while(l<r){
    int mi=l+(r-l+1)/2;
    if(ok(mi)){
        l=mi;
    }else{
        r=mi-1;
    }
}
cout<<l<<endl;


}

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