Submission #674886

#	Time	Username	Problem	Language	Result	Execution time	Memory
674886		penguin133	Exhibition (JOI19_ho_t2)	C++14	100 / 100	321 ms	7452 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second

int n, m;
pi A[200005];
int B[200005];
int32_t main(){
	cin >> n >> m;
	for(int i=1;i<=n;i++)cin >> A[i].fi >> A[i].se;
	sort(A+1, A+n+1);
	for(int i=1;i<=m;i++)cin >> B[i];
	sort(B+1, B+m+1);
	int lo = 1, hi = min(n, m), ans = lo - 1;
	while(lo <= hi){
		int mid = (lo + hi)>>1;
		int in = 1;
		priority_queue<int, vector<int>, greater<int> >pq;
		int pre = 0;
		bool f = 1;
		for(int i=m-mid+1;i<=m;i++){
			while(in <= n && A[in].fi <= B[i])pq.push(A[in].se), in++;
			if(pq.empty())f = 0;
			else{
				while(!pq.empty() && pq.top() < pre)pq.pop();
				if(pq.empty())f = 0;
				else pre = pq.top(), pq.pop();
			}
		}
		if(f)lo = mid + 1, ans= mid;
		else hi = mid - 1;
	}
	cout << ans;
}

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