#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;//wrong yerse N i değiştirmeyi unutma
const int inf = 1e9 + 7;
struct SEGT{
vector < int > tree;
int sz;
SEGT(int x){
sz = x+3;
tree.assign(4*sz , inf);
}
int _query(int ind , int l , int r , int ql , int qr){
if(l >= ql and r <= qr)return tree[ind];
else if(l > qr or r < ql)return inf;
int mid = (l+r)/2;
return min(_query(ind*2,l,mid,ql,qr) , _query(ind*2+1,mid+1,r,ql,qr));
}
int query(int l , int r){
return _query(1,1,sz,l,r);
}
void _update(int ind , int l , int r , int qp , int qv){
if(l == r){
tree[ind] = qv;
return;
}
int mid = (l+r)/2;
if(mid >= qp)_update(ind*2,l,mid,qp,qv);
else _update(ind*2+1,mid+1,r,qp,qv);
tree[ind] = min(tree[ind*2] , tree[ind*2+1]);
}
void update(int p , int v){
_update(1,1,sz,p,v);
}
};
int n , m , frame[N];
pair < int , int > picture[N];
vector < int > comp;
bool check(int x){
SEGT segt(N);
vector < int > ind[N];
for(int i = 0;i<n;i++){
ind[picture[i].second].push_back(i);
}
for(int i = 0;i<N;i++){
if(ind[i].size()){
sort(ind[i].begin() , ind[i].end());
reverse(ind[i].begin() , ind[i].end());
segt.update(i,ind[i].back());
}
}
int last = 0;
for(int i = m-x;i<m;i++){
int nxt = segt.query(1,frame[i]);
if(nxt == inf)return 0;
while(last <= nxt){
ind[picture[last].second].pop_back();
if(ind[picture[last].second].size()){
segt.update(picture[last].second , ind[picture[last].second].back());
}
else{
segt.update(picture[last].second , inf);
}
last++;
}
}
return 1;
}
void solve(){
cin >> n >> m;
for(int i = 0;i<n;i++){
cin >> picture[i].second >> picture[i].first;
comp.push_back(picture[i].second);
}
for(int i = 0;i<m;i++){
cin >> frame[i];
comp.push_back(frame[i]);
}
sort(comp.begin() , comp.end());
comp.resize(unique(comp.begin() , comp.end()) - comp.begin());
for(int i = 0;i<n;i++){
picture[i].second = lower_bound(comp.begin() , comp.end() , picture[i].second) - comp.begin() + 1;
}
for(int i = 0;i<m;i++){
frame[i] = lower_bound(comp.begin() , comp.end() , frame[i]) - comp.begin() + 1;
}
sort(frame , frame + m);
sort(picture , picture + n);
int l = 0 , r = n , ans = 0;
while(l < r){
int mid = (l+r)/2;
if(check(mid)){
ans = mid;
l = mid+1;
}
else r = mid;
}
cout << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4184 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4188 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4184 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4188 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4184 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4188 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
