# PBinfo #1870 – easyxy – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se dă un vector v cu N elemente numere naturale numerotate de la 1 la N și M întrebări de forma:


x y p: se afișează valoarea ce s-ar afla pe poziția p dacă v[x...y] ar fi ordonat crescător.

Să se răspundă la cele M întrebări.

Date de intrare
Fișierul de intrare easyxy.in conține pe prima linie numerele N și M. Pe următoarea linie se află N elemente ce reprezintă elementele vectorului. Pe următoarele M linii se află întrebările.

Date de ieșire
Fișierul de ieșire easyxy.out va conține pe fiecare linie i răspunsul la întrebarea i, în ordinea în care acestea apar în fișierul de intrare.

Restricții și precizări

1 ≤ N,M ≤ 100.000
Elementele vectorului sunt ≤ 1.000.000.000
Pentru orice întrebare, 1 ≤ x ≤ p ≤ y ≤ N

Exemplu:
easyxy.in

6 3
1 3 2 5 6 3
1 3 2
1 6 5
3 5 4
easyxy.out

2
5
5

## Cod sursă C++

```cpp
// Popa Bogdan Ioan clasa a 10-a, Colegiul National Aurel Vlaicu
#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];
int a[nmax];
int n,m;
int i;
void build(int nod, int st, int dr)
{
    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)
{
    if(a<=st && dr<=b)
    {
        int p=upper_bound(arb[nod].begin(),arb[nod].end(),val)-arb[nod].begin();
        lwr+=p;
        if(p!=0)
            if(arb[nod][p-1]==val)ok=1;
        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)
{
    int s=1,d=n,m,best=-1;
    while(s<=d)
    {
        m=s+(d-s)/2;
        lwr=0;
        ok=0;
        query(1,1,n,st,dr,a[m]);
        if(st+lwr-1>=poz)
        {
            if(ok==1)
            {
                best=a[m];
                if(st+lwr-1==poz)return a[m];
            }
            d=m-1;
        }
        else s=m+1;
    }
    return best;
}
int x,y,p;
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
        fin>>a[i];
    build(1,1,n);
    for(i=1;i<=n;i++)
        a[i]=arb[1][i-1];
    while(m--)
    {
        fin>>x>>y>>p;
        fout<<sol(x,y,p)<<"\n";
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1870)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1870/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1870/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)