Submission #92303

#TimeUsernameProblemLanguageResultExecution timeMemory
92303maruiiMatryoshka (JOI16_matryoshka)C++17
0 / 100
2 ms376 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...