This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
const int inf = 1e18;
int n,m;
vector<pair<int,int> > paintings;
vector<int> frames;
bool check(int k){
H(k);
priority_queue<int> pq;
int j = 0;
int ma = 0;
for(int i = m-k; i<m; i++){
while(j<n && paintings[j].first <= frames[i]){
pq.push(-paintings[j++].second);
P('&');
}
while(!pq.empty() && -pq.top() < ma){
pq.pop();
P('b');
}
if(pq.empty()){
P('#');
return false;
}
ma = max(ma, -pq.top());
pq.pop();
}
return true;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
paintings.resize(n);
frames.resize(m);
F(i,n){
cin>>paintings[i].first>>paintings[i].second;
}
F(i,m){
cin>>frames[i];
}
sort(paintings.begin(),paintings.end());
sort(frames.begin(),frames.end());
int res = 0;
for(int bs = 1<<20; bs>0; bs/=2) if(res+bs <= m && check(res+bs)){
res+=bs;
}
cout<<res<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |