fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef vector <int> vi;
  6. typedef vector<vi> vvi;
  7. typedef pair<int,int> ii;
  8. #define pb push_back
  9. #define INF 100000000
  10. #define mp make_pair
  11. #define MOD 1000000007
  12. #define F first
  13. #define S second
  14.  
  15. int n;
  16. ll a[100005];
  17. ll total[200005];
  18. ll ans[200005];
  19. ll pref[200005];
  20. ll suff[200005];
  21.  
  22. int main() {
  23.  
  24. 	ios::sync_with_stdio(false);
  25.     cin >> n;
  26.     int x = 1;
  27.     while (x < n) x *= 2;
  28.  
  29.     for (int i = 0; i < n; i ++) cin >> a[i];
  30.     for (int i = n; i < x; i++) a[i] = -(INF*INF);
  31.  
  32.     n = x;
  33.  
  34.     for (int i = n; i < 2*n; i++) total[i] = a[i-n];
  35.     for (int i = n-1; i > 0; i--) total[i] = total[i*2]+total[i*2+1];
  36.  
  37.     for (int i = n; i < 2*n; i++) pref[i] = a[i-n];
  38.     for (int i = n-1; i > 0; i--) pref[i] = max(pref[i*2],total[i*2]+pref[i*2+1]);
  39.  
  40.     for (int i = n; i < 2*n; i++) suff[i] = a[i-n];
  41.     for (int i = n-1; i > 0; i--) suff[i] = max(suff[i*2+1],total[i*2+1]+suff[i*2]);
  42.  
  43.     for (int i = n; i < 2*n; i++) ans[i] = a[i-n];
  44.     for (int i = n-1; i > 0; i--) ans[i] = max(suff[i*2]+pref[i*2+1],
  45.                                                max(ans[i*2],ans[i*2+1])
  46.                                                );
  47.  
  48.     // for (int i = 0; i < 2*n; i++) cout << i << " - " << ans[i] << endl;
  49.  
  50.     int m;
  51.     cin >> m;
  52.     while (m --){
  53.         ll l,r;
  54.         cin >> l >> r;
  55.         l --;
  56.         l += n;
  57.         r += n;
  58.         ll res = -(INF*INF);
  59.         ll prev = res;
  60.         vector<ll> R1,R2;
  61.  
  62.         while (l < r){
  63.             if (l%2 == 1){
  64.                 // res = max(res,ans[l++]);
  65.                 l++;
  66.                 R1.pb(l-1);
  67.             }
  68.             if (r%2 == 1){
  69.                 // res = max(res,ans[--r]);
  70.                 --r;
  71.                 R2.pb(r);
  72.             }
  73.  
  74.             // cout << l << " " << r << " " << res << endl;
  75.  
  76.             l /= 2;
  77.             r /= 2;
  78.         }
  79.  
  80.         for (int i = R2.size()-1; i >= 0; i --) R1.pb(R2[i]);
  81.  
  82.         for (int i = 0; i < R1.size(); i++){
  83.             res = max(res,ans[R1[i]]);
  84.             res = max(res,prev+pref[R1[i]]);
  85.             prev = max(prev+total[R1[i]],suff[R1[i]]);
  86.         }
  87.  
  88.         cout << res << endl;
  89.     }
  90. }
Success #stdin #stdout 0s 22272KB
comments (?)
stdin
copy 
10
-1 9 2 6 -4 3 5 2 -6 1
1
4 7
stdout
copy 
10
https://ideone.com/H2wjUT
language:
C++14 (clang 8.0)
created:
7 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!