fork download
copy 
  1.  #include <bits/stdc++.h>
  2.  
  3.     using namespace std;
  4.  
  5.     const int N = 1e5;  // limit for array size
  6.     int n;  // array size
  7.     int t[2 * N];
  8.     int t_ans[2*N];
  9.  
  10.     void build1() {  // build the tree
  11.       for (int i = n - 1; i > 0; --i) t[i] = max(t[i<<1],t[i<<1|1]);
  12.     }
  13.  
  14.     void build2() {  // build the tree
  15.       for (int i = n - 1; i > 0; --i) t_ans[i] = t[i<<1] - t[i<<1|1];
  16.     }
  17.  
  18.     void modify(int p, int value) {  // set value at position p
  19.       for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
  20.     }
  21.  
  22.     int query(int l, int r) {  // sum on interval [l, r)
  23.       int res = 0;
  24.       for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  25.         if (l&1) res = max(res,t[l++]);
  26.         if (r&1) res = max(res,t[--r]);
  27.       }
  28.       return res;
  29.     }
  30.  
  31.     int query2(int l, int r) {  // sum on interval [l, r)
  32.       int res = 0;
  33.       for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  34.         if (l&1) res = max(res, t_ans[l++]);
  35.         if (r&1) res = max(res, t_ans[--r]);
  36.       }
  37.       return res;
  38.     }
  39.  
  40.     int main() {
  41.       cin>>n;
  42.       for (int i = 0; i < n; ++i) {
  43.         scanf("%d", t + n + i);
  44.       }
  45.       build1();
  46.       build2();
  47.  
  48.       /*
  49.       For testing purpose only
  50.       for(int i=0; i<2*n; i++) {
  51.         cout<<t[i]<<" ";
  52.       }
  53.       cout<<endl;
  54.       for(int i=0; i<2*n; i++) {
  55.         cout<<t_ans[i]<<" ";
  56.       }
  57.       cout<<endl;
  58.       */
  59.       int q;
  60.       cin>>q;
  61.       for(int i=0; i<q; i++) {
  62.         int l,r;
  63.         cin>>l>>r;
  64.         cout<<query2(l,r+1)<<endl;
  65.       }
  66.  
  67.       return 0;
  68.     }
Success #stdin #stdout 0s 16800KB
comments (?)
stdin
copy 
5
10 2 11 7 8
3
0 2
1 3
2 3
stdout
copy 
0
0
0
https://ideone.com/6bbF8H
language:
C++14 (gcc 8.3)
created:
6 years 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!