Submission #336803

#	Time	Username	Problem	Language	Result	Execution time	Memory
336803		Dormi	Exhibition (JOI19_ho_t2)	C++14	100 / 100	71 ms	4588 KiB

joi2019_ho_t2

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
int sz(const T &a){return int(a.size());}
const int MN=1e5+1;
pii arr[MN];
int frame[MN];
int n,m;
bool work(int am){
    int ptr=m-am;
    for(int i=0;i<n;i++){
        if(arr[i].second<=frame[ptr])ptr++;
    }
    return ptr==m;
}
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>arr[i].second>>arr[i].first;
    for(int i=0;i<m;i++)cin>>frame[i];
    sort(arr,arr+n),sort(frame,frame+m);
    int lo=0,hi=min(m,n);
    while(lo!=hi){
        int mid=(lo+hi+1)/2;
        if(work(mid))lo=mid;
        else hi=mid-1;
    }
    printf("%d\n",lo);
    return 0;
}

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