Submission #744457

#	Time	Username	Problem	Language	Result	Execution time	Memory
744457		MODDI	Exhibition (JOI19_ho_t2)	C++14	100 / 100	351 ms	6580 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m;
vector<pll> arr;
vl frame;
bool can(int x){
	int j = 1, prev = 0;
	priority_queue<int, vector<int>, greater<int>> pq;
	for(int i = m-x+1; i <= m; i++){
		while(j <= n && arr[j].first <= frame[i]){
			pq.push(arr[j].second);
			j++;
		}
		if(pq.empty())	return false;
		else{
			while(!pq.empty() && (pq.top() < prev)){
				pq.pop();
			}
			if(pq.empty())	return false;
			else{
				prev = pq.top();
				pq.pop();
			}
		}
	}
	return true;
}
int main(){
	cin>>n>>m;
	arr.resize(n+1);
	frame.resize(m+1);
	for(int i = 1; i <= n; i++){
		cin>>arr[i].first>>arr[i].second;
	}
	for(int i = 1; i <= m; i++){
		cin>>frame[i];
	}
	sort(frame.begin(), frame.end());
	sort(arr.begin(), arr.end());
	int l = 1, r = min(n, m), ans = 0;
	while(l <= r){
		int mid = (l + r) / 2;
		bool can1 = can(mid);
		if(can1){
			ans = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	cout<<ans<<endl;
	return 0;
}

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