Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- void build(vector<pair<int, int>>& tree, int idx, int l, int r, vector<int>& a){
- if (r-l==1){
- tree[idx]={a[l], l};
- return;
- }
- int m=(l+r)/2;
- build(tree, 2*idx+1, l, m, a);
- build(tree, 2*idx+2, m, r, a);
- tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
- }
- void change(vector<pair<int, int>>& tree, int l, int r, int idx, int i, int x){
- if (i<l || i>=r){
- return;
- }
- if (r-l==1){
- tree[idx]={x, i};
- return;
- }
- int m=(l+r)/2;
- change(tree, l, m, 2*idx+1, i, x);
- change(tree, m, r, 2*idx+2, i, x);
- tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
- }
- pair<int, int> ans(vector<pair<int, int>>& tree, int idx, int l, int r, int L, int R){
- if (R<=l || L>=r){
- return {-1, -1};
- }
- if (l>=L && r<=R){
- return tree[idx];
- }
- int m=(l+r)/2;
- return max(ans(tree, 2*idx+1, l, m, L, R), ans(tree, 2*idx+2, m, r, L, R));
- }
- int main(){
- int n;
- cin>>n;
- vector<int> a(n);
- for (int i=0; i<n; i++){
- cin>>a[i];
- }
- int k;
- cin>>k;
- vector<pair<int, int>> tree(4*n);
- build(tree, 0, 0, n, a);
- while(k--){
- int l, r;
- cin>>l>>r;
- l--;
- cout<<ans(tree, 0, 0, n, l, r).first<<" "<<ans(tree, 0, 0, n, l, r).second+1<<"\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement