fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ff first
  4. #define ss second
  5.  
  6. #define oo 1000000007
  7.  
  8. using namespace std;
  9.  
  10. class wavelet{
  11.     int n, small, large;
  12.     vector<vector<int> > wt, l, r;
  13.  
  14.     void build(int p, int L, int R, const vector<int>& v){
  15.         if(R <= L) return;
  16.         wt[p].assign(v.size()+1, 0);
  17.         l[p].assign(v.size()+1, 0);
  18.         r[p].assign(v.size()+1, 0);
  19.         int mid = (L+R)/2;
  20.         vector<int> left, right;
  21.         int c = 0;
  22.         for(int i = 0; i < v.size(); i++){
  23.             if(v[i] <= mid){
  24.                 left.push_back(v[i]);
  25.                 c++;
  26.             }
  27.             else{
  28.                 right.push_back(v[i]);
  29.             }
  30.             l[p][i+1] = c, r[p][i+1] = i+1-c;
  31.         }
  32.         build(2*p, L, mid, left);
  33.         build(2*p+1, mid+1, R, right);
  34.     }
  35.  
  36.     int find(int p, int L, int R, int i, int j, int k){
  37.         if(L == R) return L;
  38.         int mid = (L+R)/2;
  39.         int c = l[p][j] - l[p][i-1];
  40.         if(c >= k) return find(2*p, L, mid, l[p][i-1]+1, l[p][j], k);
  41.         else return find(2*p+1, mid+1, R, r[p][i-1]+1, r[p][j], k - c);
  42.     }
  43.  
  44. public:
  45.     wavelet(vector<int> &v) : n(v.size()), wt(4*v.size()), l(4*v.size()), r(4*v.size()){
  46.         small = oo;
  47.         large =-oo;
  48.         for(int i = 0; i < v.size(); i++)
  49.             small = min(small, v[i]),
  50.             large = max(large, v[i]);
  51.         build(1, small, large, v);
  52.     }
  53.  
  54.     int find(int i, int j, int k){
  55.         return find(1, small, large, i, j, k);
  56.     }
  57. };
  58.  
  59. int main(){
  60.  
  61.     int n, m;
  62.  
  63.     scanf("%d %d", &n, &m);
  64.     vector<int> v(n);
  65.  
  66.     for(int i = 0; i < n; i++)
  67.         scanf("%d", &v[i]);
  68.  
  69.     {
  70.         set<int> s;
  71.         for(int i = 0; i < n; i++) s.insert(v[i]);
  72.         map<int, int> go;
  73.         int ptr = 1;
  74.         for(int x : s) go[x] = ptr++;
  75.         for(int i = 0; i < n; i++) v[i] = go[ v[i] ];
  76.     }
  77.  
  78.     wavelet wt(v);
  79.  
  80.     for(int i = 0; i < m; i++){
  81.         int l, r, k;
  82.         scanf("%d %d %d", &l, &r, &k);
  83.         printf("%d\n", wt.find(l, r, k));
  84.     }
  85.  
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0s 15256KB
comments (?)
stdin
copy 
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
stdout
copy 
5
6
3
https://ideone.com/w7WY1R
problem MKTHNUM, based on SPOJ submission 19803934 (CPP14), 2017-07-15 23:41:01
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!