fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Fenwick {
  5.     int n;
  6.     vector<int> bit;
  7.     Fenwick(int n): n(n), bit(n+1,0) {}
  8.     void update(int i,int val){
  9.         for(;i<=n;i+=i&-i) bit[i]=max(bit[i],val);
  10.     }
  11.     int query(int i){
  12.         int res=0;
  13.         for(;i>0;i-=i&-i) res=max(res,bit[i]);
  14.         return res;
  15.     }
  16. };
  17.  
  18. int main(){
  19.     ios::sync_with_stdio(false);
  20.     cin.tie(nullptr);
  21.     int N; cin>>N;
  22.     vector<pair<int,int>> dolls(N);
  23.     for(int i=0;i<N;i++) cin>>dolls[i].first>>dolls[i].second;
  24.     int Q; cin>>Q;
  25.     vector<tuple<int,int,int>> queries(Q);
  26.     for(int i=0;i<Q;i++){
  27.         int A,B; cin>>A>>B;
  28.         queries[i]= {A,B,i};
  29.     }
  30.     vector<int> vals;
  31.     for(auto &p:dolls) vals.push_back(p.second);
  32.     for(auto &q:queries) vals.push_back(get<1>(q));
  33.     sort(vals.begin(),vals.end());
  34.     vals.erase(unique(vals.begin(),vals.end()),vals.end());
  35.     auto compress=[&](int x){
  36.         return int(lower_bound(vals.begin(),vals.end(),x)-vals.begin())+1;
  37.     };
  38.     vector<array<int,3>> D;
  39.     for(auto &p:dolls) D.push_back({p.first,compress(p.second),p.second});
  40.     sort(D.begin(),D.end(),[&](auto &a,auto &b){
  41.         if(a[0]!=b[0]) return a[0]>b[0];
  42.         return a[2]>b[2];
  43.     });
  44.     vector<array<int,4>> Qs;
  45.     for(auto &q:queries){
  46.         int A,B,id; tie(A,B,id)=q;
  47.         Qs.push_back({A,compress(B),B,id});
  48.     }
  49.     sort(Qs.begin(),Qs.end(),[&](auto &a,auto &b){return a[0]>b[0];});
  50.     Fenwick bit(vals.size());
  51.     vector<int> ans(Q);
  52.     int idx=0;
  53.     for(auto &qq:Qs){
  54.         int A=qq[0],B=qq[1],id=qq[3];
  55.         while(idx<N && D[idx][0]>=A){
  56.             int h=D[idx][1];
  57.             int best=bit.query(h-1)+1;
  58.             bit.update(h,best);
  59.             idx++;
  60.         }
  61.         ans[id]=bit.query(B);
  62.     }
  63.     for(int x:ans) cout<<x<<"\n";
  64. }
  65.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6
4 1
2 2
6 4
6 1
1 3
5 2
1
3 5
stdout
copy 
2
https://ideone.com/9LBvF6
language:
C++14 (clang 8.0)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!