easyxy

/// Popa Bogdan Ioan clasa a 10-a, Colegiul National Aurel Vlaicu

/// Se da un vector v cu N elemente numere naturale numerotate de la 1 la N si M întrebari de forma:
/// x y p: se afiseaza valoarea ce s-ar afla pe pozitia p daca v[x...y] ar fi ordonat crescator.
/// Sa se raspunda la cele M întrebari.

#include <bits/stdc++.h>
#define nmax 100002
#define vmax 1000000000
#define pb push_back
using namespace std;
ifstream fin("easyxy.in");
ofstream fout("easyxy.out");
vector <int> arb[4*nmax+55]; /// Arborele de intervale
int a[nmax];  /// Vectorul care memoreaza cele n numere
int n,m; /// n-numarul de element; m-numarul de intrebari

void build(int nod,int st,int dr)  /// Construieste arborele de intervale
{
    if(st==dr)
    {
        arb[nod].pb(a[st]);
        return;
    }
    int mij=(st+dr)/2;
    build(2*nod,st,mij);
    build(2*nod+1,mij+1,dr);
    int i,j;
    for(i=0,j=0;i<(int)arb[2*nod].size()&&j<(int)arb[2*nod+1].size();)
    {
        if(arb[2*nod][i]<=arb[2*nod+1][j])
            arb[nod].pb(arb[2*nod][i++]);
        else
            arb[nod].pb(arb[2*nod+1][j++]);
    }
    while(i<(int)arb[2*nod].size())
        arb[nod].pb(arb[2*nod][i++]);
    while(j<(int)arb[2*nod+1].size())
        arb[nod].pb(arb[2*nod+1][j++]);
}

int lwr;
bool ok;
void query(int nod,int st,int dr,int a,int b,int val) /// Interogare arbore de intervale
{
    if(a<=st&&dr<=b)
    {
        int pozitia=upper_bound(arb[nod].begin(),arb[nod].end(),val)-arb[nod].begin();
        lwr+=pozitia;
        if(pozitia!=0)
            if(arb[nod][pozitia-1]==val)
                ok=true;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        query(2*nod,st,mij,a,b,val);
    if(b>mij)
        query(2*nod+1,mij+1,dr,a,b,val);
}

int sol(int st,int dr,int poz) /// Cautare binara pentru gasirea unei solutii (st-limita din stanga (x); dr-limita din drapta (y))
{
    int s=1,d=n,mijloc,best=-1; /// s-stanga; d-dreapta; best-valoarea care s-ar afla pe pozitia poz
    while(s<=d)
    {
        mijloc=s+(d-s)/2; /// mijloc-mijlocul intervalului
        lwr=0;
        ok=false;
        query(1,1,n,st,dr,a[mijloc]);
        if(st+lwr-1>=poz)
        {
            if(ok)
            {
                best=a[mijloc];
                if(st+lwr-1==poz)
                    return a[mijloc];
            }
            d=mijloc-1;
        }
        else
            s=mijloc+1;
    }
    return best;
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    build(1,1,n);
    for(int i=1;i<=n;++i)
        a[i]=arb[1][i-1];
    int x,y,p;
    while(m--)  /// Cele m interogari
    {
        fin>>x>>y>>p;  /// Citesc intervalul [x,y] si poozitia p
        fout<<sol(x,y,p)<<'\n';  /// Afisez solutia pentru un interval
    }
    return 0;
}