easyxy

#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#define Nmax 100005
#define Bmax 320
#define pb push_back
#define INF 2147000000
using namespace std;

vector< int > v[Bmax],aux;
int N,M,buc,sz[Bmax],este[Nmax];
int a[Nmax],aa[Nmax],ind[Nmax],Where[Nmax];

inline int cmp(int i,int j){ return aa[i]< aa[j]; }

inline void Query(int l,int r,int k){
    int i,j,p1,p2;

    for(i=1;i<=buc;++i){
        p1=lower_bound(v[i].begin(), v[i].end(), l)-v[i].begin();
        if( v[i][p1]<l ) p1++;
        p2=upper_bound(v[i].begin(), v[i].end(), r)-v[i].begin();

        if( p2-p1 < k ) k -= p2-p1;
        else break; // elem cautat de in v[i]
    }

    aux.clear();
    for(j=p1; j<p2; ++j) // j<n-1
            aux.pb(aa[v[i][j]]);

    nth_element(aux.begin(),aux.begin()+k-1,aux.end());
    printf("%d\n",*(aux.begin()+k-1));
}

int main()
{
    int i,j,Sqrt,x,y,k,cate=0;
    freopen("easyxy.in","r",stdin);
    freopen("easyxy.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;++i)
        scanf("%d",&aa[i]),ind[i]=i,este[i]=1;
    sort(ind+1,ind+N+1,cmp);
    // normalizare
    for(i=1;i<=N;++i)
       // if(aa[ind[i]]==aa[ind[i-1]]) a[ind[i]]=a[ind[i-1]];
       // else
       a[ind[i]]=i;

    //Sqrt=sqrt(N);
    Sqrt=900;
    j=1; buc=0; // repartizare indici in galeti dupa valoarea idului
    for(i=1; j<=N; i+=Sqrt){
        ++buc;
        for( ; j<=N && a[ind[j]] < i+Sqrt; ++j){
            v[buc].pb(ind[j]);
            sz[buc]++;
            Where[ind[j]]=buc;
        }
        sort(v[buc].begin(),v[buc].end());
        v[buc].pb(INF); // ma ajuta la update
    }

    for(i=1;i<=buc;++i) cate+=sz[i];

    for(i=1;i<=M;++i)
    {
        scanf("%d%d%d",&x,&y,&k);
        k=k-x+1;
        Query(x,y,k);
    }

    fclose(stdin); fclose(stdout);
    return 0;
}