fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define MAX 1000001
  5. vector<ll> seg[MAX];
  6. vector<ll> q;
  7.  
  8. void build(ll a[],ll low,ll high,ll pos)
  9. {
  10.   if(low==high)
  11.   {
  12.     seg[pos].push_back(a[low]);
  13.     return;
  14.   }
  15.   ll mid=(low+high)/2;
  16.   build(a,low,mid,2*pos+1);
  17.   build(a,mid+1,high,2*pos+2);
  18.   merge(seg[2*pos+1].begin(),seg[2*pos+1].end(),seg[2*pos+2].begin(),seg[2*pos+2].end(),back_inserter(seg[pos]));
  19. }
  20.  
  21. ll query(ll low,ll high,ll qlow,ll qhigh,ll val,ll pos,ll n)
  22. {
  23.   if(qlow>high||qhigh<low)
  24.   {
  25.     return 0;
  26.   }
  27.   if(qlow<=low&&qhigh>=high)
  28.   {
  29.     q.insert(q.end(),seg[pos].begin(),seg[pos].end());
  30.     if(qlow==0&&qhigh==n-1)
  31.     {
  32.       return q[val-1];
  33.     }//upper_bound(seg[pos].begin(),seg[pos].end(),val)-seg[pos].begin();
  34.     return 0;
  35.   }
  36.   ll mid=(low+high)/2;
  37.   ll a=query(low,mid,qlow,qhigh,val,2*pos+1,n);
  38.   ll b=query(mid+1,high,qlow,qhigh,val,2*pos+2,n);
  39.   //merge(seg[2*pos+1].begin(),seg[2*pos+1].end(),seg[2*pos+2].begin(),seg[2*pos+2].end(),back_inserter(q));
  40.   /*for(ll i=0;i<q.size();i++)
  41.   {
  42.     cout<<q[i]<<" ";
  43.   }
  44.   cout<<endl;*/
  45.   sort(q.begin(),q.end());
  46.   return q[val-1];
  47. }
  48.  
  49. int main()
  50. {
  51.   ll n,m,x,y,k;
  52.   cin>>n>>m;
  53.   ll a[n];
  54.   for(ll i=0;i<n;i++)
  55.   {
  56.     cin>>a[i];
  57.   }
  58.   build(a,0,n-1,0);
  59.   /*for(ll i=0;i<2*n-1;i++)
  60.   {
  61.     cout<<i<<" : ";
  62.     for(ll j=0;j<seg[i].size();j++)
  63.     {
  64.       cout<<seg[i][j]<<" ";
  65.     }
  66.     cout<<endl;
  67.   }*/
  68.   while(m--)
  69.   {
  70.     cin>>x>>y>>k;
  71.     cout<<query(0,n-1,x-1,y-1,k,0,n)<<endl;
  72.     q.clear();
  73.   }
  74. }
Runtime error #stdin #stdout 0s 38680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JLNF6b
language:
C++14 (gcc 8.3)
created:
6 years 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!