Advertisement
Promi_38

st-find the minimum

Nov 23rd, 2021
714
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include<bits\stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<long long> tree;
  6.  
  7. long long get_min(int cur_node, int q_low, int q_high, int cur_low, int cur_high){
  8.    
  9.    
  10.     if(q_low <= cur_low && q_high >= cur_high) return tree[cur_node];
  11.     else if(q_low > cur_high || q_high < cur_low) return 999999;
  12.     else return min(get_min(cur_node*2, q_low, q_high, cur_low, (cur_high+cur_low)/2), get_min(cur_node*2 + 1, q_low, q_high, (cur_high+cur_low)/2 + 1, cur_high));
  13. }
  14.  
  15. int main()
  16. {
  17.     long long t, j;
  18.     cin >> t;
  19.     for(j = 1; j <= t; j++)
  20.     {
  21.         long long n, q;
  22.     cin >> n >> q;
  23.     long long i, x;
  24.     vector < long long> v;
  25.     for(i = 0; i < n; i++)
  26.     {
  27.         cin >> x;
  28.         v.push_back(x);
  29.     }
  30.     while(__builtin_popcount(n) != 1)
  31.     {
  32.         n++;
  33.         v.push_back(999999LL);
  34.     }
  35.     tree.resize(2 * n);
  36.     //for(i = 0; i < n; i++) cout << v[i] << " ";
  37.     for(i = n; i < 2*n; i++) tree[i] = v[i-n];
  38.     for(i = n - 1; i > 0; i--) tree[i] = min(tree[2*i], tree[2*i + 1]);
  39.  
  40.     printf("Case %lld: \n", j);
  41.     while(q--)
  42.     {
  43.         long long l, r;
  44.         cin >> l >> r;
  45.         cout << get_min(1, l, r, 1, n) << endl;
  46.     }
  47.     }
  48.    
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement