Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits\stdc++.h>
- using namespace std;
- vector<long long> tree;
- long long get_min(int cur_node, int q_low, int q_high, int cur_low, int cur_high){
- if(q_low <= cur_low && q_high >= cur_high) return tree[cur_node];
- else if(q_low > cur_high || q_high < cur_low) return 999999;
- 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));
- }
- int main()
- {
- long long t, j;
- cin >> t;
- for(j = 1; j <= t; j++)
- {
- long long n, q;
- cin >> n >> q;
- long long i, x;
- vector < long long> v;
- for(i = 0; i < n; i++)
- {
- cin >> x;
- v.push_back(x);
- }
- while(__builtin_popcount(n) != 1)
- {
- n++;
- v.push_back(999999LL);
- }
- tree.resize(2 * n);
- //for(i = 0; i < n; i++) cout << v[i] << " ";
- for(i = n; i < 2*n; i++) tree[i] = v[i-n];
- for(i = n - 1; i > 0; i--) tree[i] = min(tree[2*i], tree[2*i + 1]);
- printf("Case %lld: \n", j);
- while(q--)
- {
- long long l, r;
- cin >> l >> r;
- cout << get_min(1, l, r, 1, n) << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement