Adrita

ds lab 9 task 2

Jul 28th, 2020
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.87 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int tree[2000];
  5. int ar[1000];
  6. void init(int node,int b,int e)
  7. {
  8. if(b==e)
  9. {
  10. tree[node]=ar[b];
  11. return;
  12. }
  13. int left=node*2;
  14. int right=(node*2)+1;
  15. int mid=(b+e)/2;
  16. init(left,b,mid);
  17. init(right,mid+1,e);
  18. tree[node]=min(tree[left],tree[right]);
  19. }
  20. int query_min(int node,int b,int e,int i,int j)
  21. {
  22. if(i>e||j<b)
  23. return INT_MAX;
  24. if(b>=i&&e<=j)
  25. return tree[node];
  26. int left=node*2;
  27. int right=(node*2)+1;
  28. int mid=(b+e)/2;
  29. int p1=query_min(left,b,mid,i,j);
  30. int p2=query_min(right,mid+1,e,i,j);
  31. return min(p1,p2);
  32. }
  33. int main()
  34. {
  35. int k,n,Q,i,j;
  36. cin>>n>>Q;
  37. for(k=1;k<=n;k++)
  38. cin>>ar[k];
  39. init(1,1,n);
  40. while(Q--)
  41. {
  42. cin>>i>>j;
  43. cout<<query_min(1,1,n,i,j)<<endl;
  44. }
  45. }
  46.  
Add Comment
Please, Sign In to add comment