fork download
copy 
  1.     #include <bits/stdc++.h>
  2.     using namespace std;
  3.  
  4.     typedef 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.     	freopen("C:\\Users\\Shraeyas\\Documents\\pg\\pr_ag\\prag_gss1.txt", "r", stdin);
  25.  
  26.     	ios::sync_with_stdio(false);
  27.         cin >> n;
  28.         int x = 1;
  29.         while (x < n) x *= 2;
  30.  
  31.         for (int i = 0; i < n; i ++) cin >> a[i];
  32.         for (int i = n; i < x; i++) a[i] = -(INF);
  33.  
  34.         n = x;
  35.  
  36.         for (int i = n; i < 2*n; i++) total[i] = a[i-n];
  37.         for (int i = n-1; i > 0; i--) total[i] = total[i*2]+total[i*2+1];
  38.  
  39.         for (int i = n; i < 2*n; i++) pref[i] = a[i-n];
  40.         for (int i = n-1; i > 0; i--) pref[i] = max(pref[i*2],total[i*2]+pref[i*2+1]);
  41.  
  42.         for (int i = n; i < 2*n; i++) suff[i] = a[i-n];
  43.         for (int i = n-1; i > 0; i--) suff[i] = max(suff[i*2+1],total[i*2+1]+suff[i*2]);
  44.  
  45.         for (int i = n; i < 2*n; i++) ans[i] = a[i-n];
  46.         for (int i = n-1; i > 0; i--) ans[i] = max(suff[i*2]+pref[i*2+1],
  47.                                                    max(ans[i*2],ans[i*2+1])
  48.                                                    );
  49.  
  50.         // for (int i = 0; i < 2*n; i++) cout << i << " - " << ans[i] << endl;
  51.  
  52.         int m;
  53.         cin >> m;
  54.         while (m --){
  55.             ll l,r;
  56.             cin >> l >> r;
  57.             l --;
  58.             l += n;
  59.             r += n;
  60.             ll res = -(INF);
  61.             ll prev = res;
  62.             long R1[100005], R2[100005], r1=0, r2=0;
  63.  
  64.             while (l < r){
  65.                 if (l%2 == 1){
  66.                     // res = max(res,ans[l++]);
  67.                     l++;
  68.                     R1[r1++] = l-1;
  69.                 }
  70.                 if (r%2 == 1){
  71.                     // res = max(res,ans[--r]);
  72.                     --r;
  73.                     R2[r2++] = r;
  74.                 }
  75.  
  76.                 // cout << l << " " << r << " " << res << endl;
  77.  
  78.                 l /= 2;
  79.                 r /= 2;
  80.             }
  81.  
  82.             for (long i = r2-1; i >= 0; i --) R1[r1++] = R2[i];
  83.  
  84.             for (long i = 0; i < r1; i++){
  85.                 res = max(res,ans[R1[i]]);
  86.                 res = max(res,prev+pref[R1[i]]);
  87.                 prev = max(prev+total[R1[i]],suff[R1[i]]);
  88.             }
  89.  
  90.             cout << res << endl;
  91.         }
  92.     }
Runtime error #stdin #stdout #stderr 0s 24544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/kUy1h1
language:
C++ (gcc 8.3)
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!