#include <bits/stdc++.h>
using namespace std;
struct query{
int a,b,idx;
}a[200001];
struct doll{
int r,h;
}d[200001];
int n,q,res[200001],f[200001];
vector <int> v;
void update(int i, int val){
for (;i<=n;i+=i&(-i))
f[i]=max(f[i],val);
}
int get(int i){
int res=0;
for (;i;i-=i&(-i))
res=max(res,f[i]);
return res;
}
int main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> n >> q;
for (int i=1;i<=n;i++){
cin >> d[i].r >> d[i].h;
v.push_back(d[i].h);
}
sort(d+1,d+n+1,[](doll a, doll b){return (a.r<b.r||(a.r==b.r&&a.h>b.h));});
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
for (int i=1;i<=q;i++){
cin >> a[i].a >> a[i].b;
a[i].idx=i;
}
sort(a+1,a+q+1,[](query a, query b){return a.a>b.a;});
int j=n;
for (int i=1;i<=q;i++){
for (;j&&d[j].r>=a[i].a;j--){
int pos=lower_bound(v.begin(),v.end(),d[j].h)-v.begin()+1;
update(pos,get(pos)+1);
}
res[a[i].idx]=get(upper_bound(v.begin(),v.end(),a[i].b)-v.begin());
}
for (int i=1;i<=q;i++)
cout << res[i] << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
244 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
328 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
328 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
0 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
336 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
244 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
328 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
328 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
0 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
336 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
2 ms |
340 KB |
Output is correct |
| 23 |
Correct |
3 ms |
468 KB |
Output is correct |
| 24 |
Correct |
2 ms |
420 KB |
Output is correct |
| 25 |
Correct |
2 ms |
468 KB |
Output is correct |
| 26 |
Correct |
3 ms |
468 KB |
Output is correct |
| 27 |
Correct |
2 ms |
468 KB |
Output is correct |
| 28 |
Correct |
2 ms |
472 KB |
Output is correct |
| 29 |
Correct |
2 ms |
468 KB |
Output is correct |
| 30 |
Correct |
2 ms |
340 KB |
Output is correct |
| 31 |
Correct |
2 ms |
468 KB |
Output is correct |
| 32 |
Correct |
2 ms |
468 KB |
Output is correct |
| 33 |
Correct |
2 ms |
476 KB |
Output is correct |
| 34 |
Correct |
2 ms |
468 KB |
Output is correct |
| 35 |
Correct |
2 ms |
468 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
244 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
328 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
328 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
0 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
336 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
2 ms |
340 KB |
Output is correct |
| 23 |
Correct |
3 ms |
468 KB |
Output is correct |
| 24 |
Correct |
2 ms |
420 KB |
Output is correct |
| 25 |
Correct |
2 ms |
468 KB |
Output is correct |
| 26 |
Correct |
3 ms |
468 KB |
Output is correct |
| 27 |
Correct |
2 ms |
468 KB |
Output is correct |
| 28 |
Correct |
2 ms |
472 KB |
Output is correct |
| 29 |
Correct |
2 ms |
468 KB |
Output is correct |
| 30 |
Correct |
2 ms |
340 KB |
Output is correct |
| 31 |
Correct |
2 ms |
468 KB |
Output is correct |
| 32 |
Correct |
2 ms |
468 KB |
Output is correct |
| 33 |
Correct |
2 ms |
476 KB |
Output is correct |
| 34 |
Correct |
2 ms |
468 KB |
Output is correct |
| 35 |
Correct |
2 ms |
468 KB |
Output is correct |
| 36 |
Correct |
223 ms |
12260 KB |
Output is correct |
| 37 |
Correct |
149 ms |
11204 KB |
Output is correct |
| 38 |
Correct |
66 ms |
5192 KB |
Output is correct |
| 39 |
Correct |
144 ms |
9588 KB |
Output is correct |
| 40 |
Correct |
119 ms |
10064 KB |
Output is correct |
| 41 |
Correct |
149 ms |
11132 KB |
Output is correct |
| 42 |
Correct |
107 ms |
8712 KB |
Output is correct |
| 43 |
Correct |
68 ms |
8932 KB |
Output is correct |
| 44 |
Correct |
222 ms |
15284 KB |
Output is correct |
| 45 |
Correct |
204 ms |
15220 KB |
Output is correct |
| 46 |
Correct |
214 ms |
15108 KB |
Output is correct |
| 47 |
Correct |
195 ms |
14860 KB |
Output is correct |
| 48 |
Correct |
197 ms |
15356 KB |
Output is correct |
| 49 |
Correct |
243 ms |
14868 KB |
Output is correct |
| 50 |
Correct |
193 ms |
15328 KB |
Output is correct |
