Submission #1116630

#TimeUsernameProblemLanguageResultExecution timeMemory
1116630BzslayedExhibition (JOI19_ho_t2)C++17
100 / 100
47 ms7112 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define ll long long
#define ull unsigned long long
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define coutpair(p) cout << p.first << " " << p.second << "|"

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

//greedy idea : put the largest value picture that can fit into the ith frame, starting from the largest frame.
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll n, m; cin >> n >> m;
    priority_queue<pll> pq; //{value, size}
    for (int i=0; i<n; i++){
		ll s, v; cin >> s >> v;
		pq.push({v, s});
	}
    ll c[m];
    for (int i=0; i<m; i++) cin >> c[i];
    
    sort(c, c+m, greater<ll>());
    
    ll val[m];
    for (int i=0; i<m; i++){
		while (c[i] < pq.top().second && !pq.empty()) pq.pop();
		if (pq.empty()){
			cout << i;
			return 0;
		}
		val[i] = pq.top().first; pq.pop();
		
		
		if (i == 0) continue;
		
		if (val[i] > val[i-1]){
			cout << i;
			return 0;
		}
	}
	
	cout << m;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...