Submission #124646

#TimeUsernameProblemLanguageResultExecution timeMemory
124646ioilolcomExhibition (JOI19_ho_t2)C++14
100 / 100
175 ms5752 KiB
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pii pair<ll,ll>
#define sz second
#define  val first
typedef long long int ll;
vector<pii> v;
int n,m;
vector<ll> available;
bool check(int ans){
	int cadre=m-ans;
	for(int i=0; i<n; i++) {
		if(cadre<m&&v[i].sz<=available[cadre]) {
			cadre++;
		}
	}
	return (cadre==m);
}
int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	v.resize(n);
	available.resize(m);
	for(int i=0; i<n; i++) {
		cin>>v[i].sz>>v[i].val;
	}
	sort(v.begin(),v.end());

	for(int i=0; i<m; i++) {
		cin>>available[i];
	}
	sort(available.begin(),available.end());
	// first of all if it possible to fit k pictures then they would  fit  in the largest k frames
	// so we will binary search on the answer k
	int l=0;
	int r=min(n,m);
	int ans=0;
	//cout<<check(1)<<endl;
	while(l<=r) {
		int mid=(l+r)/2;
		if(check(mid)) {
			ans=mid;
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}

	cout<<ans<<endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...