Submission #669728

#	Time	Username	Problem	Language	Result	Execution time	Memory
669728		dsyz	Art Exhibition (JOI18_art)	C++17	0 / 100	99 ms	262144 KiB

art

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M;
	cin>>N>>M;
	pair<ll,ll> arr[N]; //s, v
	for(ll i = 0;i < N;i++){
		cin>>arr[i].first>>arr[i].second;
	}
	ll C[M];
	for(ll i = 0;i < M;i++){
		cin>>C[i];
	}
	sort(arr,arr + N);
	sort(C,C + M);
	priority_queue<pair<ll,ll> > pq;
	ll ptr = -1;
	while(ptr < N - 1 && arr[ptr + 1].first <= C[M - 1]){
		ptr++;
		pq.push(make_pair(arr[ptr].second,arr[ptr].first));
	}
	ll ans = 0;
	ll prev = 1e18;
	for(ll i = M - 1;i >= 0;i--){
		while(!pq.empty() && (pq.top().first > prev || pq.top().second > C[i])){
			pq.pop();
		}
		if(!pq.empty()){
			ans++;
			pq.pop();
		}
	}
	cout<<ans<<'\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50