fork(1) 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.         int l,r;
  54.         cin >> l >> r;
  55.         l --;
  56.         l += n;
  57.         r += n;
  58.         ll res = -1500000;
  59.         while (l < r){
  60.             if (l%2) res = max(res,ans[l++]);
  61.             if (r%2) res = max(res,ans[--r]);
  62.             l /= 2;
  63.             r /= 2;
  64.         }
  65.         cout << res << endl;
  66.     }
  67. }
Success #stdin #stdout 0s 22272KB
comments (?)
stdin
copy 
10
-200 3 4 -200 6 2 4 -200 5 6
1
1 10
stdout
copy 
12
https://ideone.com/zUnx5g
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!