Submission #524653

#	Time	Username	Problem	Language	Result	Execution time	Memory
524653		thomas_li	Exhibition (JOI19_ho_t2)	C++17	100 / 100	281 ms	5312 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;
const int MM = 1e5+5;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n,m,ans = 0; cin >> n >> m;
	vector<array<int,2>> a; vector<int> b;
	for(int i = 0; i < n; i++){
		int s,v; cin >> s >> v;
		a.push_back({s,v});
	}
	for(int i = 0; i < m; i++){
		int c; cin >> c;
		b.emplace_back(c);
	}
	sort(b.begin(),b.end());
	sort(a.begin(),a.end());
	auto solve = [&](int st){
		priority_queue<int,vector<int>,greater<>> q;	
		for(int i = st, j = 0,lst = 0; i < m; i++){
			while(j < n && a[j][0] <= b[i]){
				if(lst <= a[j][1]) q.push(a[j][1]);
				j++;
			}
			if(q.empty()) return 0;
			lst = q.top();
			q.pop();
		}
		return 1;
	};
    int lo = 0, hi = m-1;
    while(lo < hi){
        int mid = (lo+hi)/2;
        if(solve(mid)) hi = mid;
        else lo = mid+1;
    }
    if(solve(lo)) cout << m-lo << "\n";
    else cout << "0\n";
}
// if ans = k, we should take k biggest frames
// we should put min value that fits in left frame, min value that fits into second left, ...

Compilation message (stderr)

joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:6:10: warning: unused variable 'ans' [-Wunused-variable]
    6 |  int n,m,ans = 0; cin >> n >> m;
      |          ^~~

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