Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// 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 elemente; m-numarul de intrebari
- void build(int nod,int st,int dr) /// Construieste arborele de intervale (nodul radacina 1)
- {
- 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 (nod=radacina; intitial st=1,dr=n;
- { /// a=x,b=y; val=valoarea din mijlocul intervalului [x,y])
- 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 (p)
- while(s<=d)
- {
- mijloc=s+(d-s)/2; /// mijloc-mijlocul intervalului [x,y]
- lwr=0;
- ok=false;
- query(1,1,n,st,dr,a[mijloc]); /// Interogare
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement