fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void build(int* tree,int i,int tl,int tr,int* a)
  6. {
  7.     if(tl==tr)
  8.     {
  9.         tree[i]=a[tl];
  10.         return ;
  11.     }
  12.     int m=(tl+tr)/2; /// tl=0 tr=7 root m=3
  13.  
  14.     /// left: tl=0 tr=m=3
  15.    build(tree,2*i+1,tl,m,a);
  16.  
  17.     /// right: tl=m+1=4 tr=7
  18.     build(tree,2*i+2,m+1,tr,a);
  19.  
  20.     tree[i]=min(tree[2*i+1],tree[2*i+2]);
  21.  
  22.  
  23.  
  24. }
  25. int query(int* tree,int i,int tl,int tr,int l,int r)
  26. {
  27.     /// full overlap
  28.     if(tl>=l && tr<=r)
  29.     {
  30.         return tree[i];
  31.     }
  32.  
  33.     /// no overlap
  34.     if(r<tl || l>tr)
  35.     {
  36.         return INT_MAX;
  37.     }
  38.  
  39.     /// partial overlap
  40.     int m=(tl+tr)/2;
  41.     int left=query(tree,2*i+1,tl,m,l,r);
  42.     int right=query(tree,2*i+2,m+1,tr,l,r);
  43.     return min(left,right);
  44. }
  45. int main()
  46. {
  47.     int n; cin >> n;
  48.     int q; cin >> q;
  49.     int a[n];
  50.     for(int i=0;i<n;i++) cin >> a[i];
  51.  
  52.     int tree[4*n];
  53.     build(tree,0,0,n-1,a);
  54.  
  55.  
  56.     while(q--)
  57.     {
  58.  
  59.             int l,r; cin >> l >> r;
  60.             l--,r--;
  61.             int ans=query(tree,0,0,n-1,l,r);
  62.             cout << ans << endl;
  63.  
  64.  
  65.     }
  66.  
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/529MUo
language:
C++ (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!