Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include<fstream>
- using namespace std;
- ifstream f("stramosi.in");
- ofstream g("stramosi.out");
- int n,q,i,v[250001],log2[20],p,k,r[250001][20],p2,j;
- inline void BuildRMQ()
- {
- int m=log2[n]+1,i,j;
- for(i=1; i<=n; i++)
- r[i][0]=v[i];
- for(j=1; j<m; j++)
- for(i=1; i<=n; i++)
- r[i][j]=r[r[i][j-1]][j-1];
- }
- inline int functie(int p,int k)
- {
- while(k && p)
- {
- bool ok=1;
- for(int i=log2[k]+1; i>=0 && ok; i--)
- if(k&(1<<i))
- {
- ok=0;
- p=r[p][log2[k]];
- k-=(1<<i);
- }
- }
- return p;
- }
- int main()
- {
- f>>n>>q;
- for(i=1; i<=n; i++)
- f>>v[i];
- log2[1]=0;
- for(i=2; i<=n; i++)
- log2[i]=log2[i/2]+1;
- BuildRMQ();
- for(; q; q--)
- {
- f>>p>>k;//al k lea stramos al lui p
- g<<functie(p,k)<<'\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement