#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> seg;
void build() {
for(int i=n-1;i>0;i--) seg[i]=max(seg[i<<1],seg[i<<1|1]);
}
void modify(int p, int value) {
for(seg[p+=n]=value;p>1;p>>=1) seg[p>>1]=max(seg[p],seg[p^1]);
}
int query(int l, int r){ // remember, this works over range [l,r)
int res=-1;
for(l+=n,r+=n;l<r;l>>=1,r>>=1){
if(l&1) res=max(res,seg[l++]); //remember, this needs to be l++, ++l will WA
if(r&1) res=max(res,seg[--r]);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m;
cin>>n>>m;
vector<pair<int,int>> pics(n);
seg.resize(2*n);
vector<int> frames(m);
for (int i=0;i<n;i++){
int a,b;
cin>>a>>b;
pics[i]={a,b};
}
sort(pics.begin(),pics.end());
for(int i=0;i<m;i++){
cin>>frames[i];
}
sort(frames.begin(),frames.end());
vector<tuple<int,int,int>> values;
for (int i=0;i<n;i++){
values[i]={pics[i].second,pics[i].first,i};
}
for (int i=0;i<n;i++){
seg[n+i]=pics[i].second;
}
build();
int res=0;
//O(n+nlogn+m+mlogm+nlogn)
for(int i=m-1;i>=0;i--){
auto it=upper_bound(pics.begin(),pics.end(),make_pair(frames[i],(int)1e9+1));
if(it==pics.begin()){
break;
}
int r=it-pics.begin();
// cerr<<r<<"\n";
int k = query(0,r);
// cerr<<k<<"\n";
if(k==-1){
break;
}
res++;
tuple<int,int,int> cur={k,frames[i],n+1};
auto it2=upper_bound(values.begin(),values.end(),cur);
it2--;
int sec=get<2>(*it2);
modify(sec,-1);
values.erase(it2);
}
cout<<res<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
