| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 92303 |
2019-01-02T13:00:20 Z |
maruii |
None (JOI16_matryoshka) |
C++17 |
|
2 ms |
376 KB |
#include<bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define ff first
#define ss second
const int SIZE = 1<<18;
struct ST{
int data[2*SIZE];
void update(int x, int v){
for(x+=SIZE; x; x/=2)
data[x] = max(data[x], v);
}
int query(int s, int e){
int ret = 0;
for(s+=SIZE, e+=SIZE; s<=e; s/=2, e/=2){
if(s&1) ret = max(ret, data[s++]);
if(~e&1) ret = max(ret, data[e--]);
}
return ret;
}
}seg;
ii p[200001];
pair<ii, int> qr[200001];
int ans[200001];
vector<int> xx,yy;
int main(){
int N,Q; scanf("%d%d",&N,&Q);
for(int i=0; i<N; ++i){
int x, y; scanf("%d%d",&x, &y);
p[i] = {-x, y};
xx.push_back(-x);
yy.push_back(y);
}
sort(xx.begin(), xx.end());
sort(yy.begin(), yy.end());
xx.erase(unique(xx.begin(), xx.end()), xx.end());
yy.erase(unique(yy.begin(), yy.end()), yy.end());
for(int i=0; i<N; ++i) p[i].ss = lower_bound(yy.begin(), yy.end(), p[i].ss) - yy.begin() + 1;
sort(p, p+N);
for(int i=0; i<Q; ++i){
int x, y; scanf("%d%d",&x,&y);
x = *(upper_bound(xx.begin(), xx.end(), -x)-1);
y = upper_bound(yy.begin(), yy.end(), y) - yy.begin();
qr[i] = {{x, y}, i};
}
sort(qr, qr+Q);
for(int i=0, j=0; i<Q; ++i){
while(j<N && p[j].ff<=qr[i].ff.ff){
seg.update(p[j].ss, seg.query(0, p[j].ss)+1);
++j;
}
ans[qr[i].ss] = seg.query(0, qr[i].ff.ss);
}
for(int i=0; i<Q; ++i) printf("%d\n",ans[i]);
return 0;
}
Compilation message
matryoshka.cpp: In function 'int main()':
matryoshka.cpp:27:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N,Q; scanf("%d%d",&N,&Q);
~~~~~^~~~~~~~~~~~~~
matryoshka.cpp:29:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d%d",&x, &y);
~~~~~^~~~~~~~~~~~~~~
matryoshka.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
