fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll          long long
  4. #define pb          push_back
  5. #define mp          make_pair
  6. #define pii         pair<int,int>
  7. #define vi          vector<int>
  8. #define all(a)      (a).begin(),(a).end()
  9. #define lol         1000000007
  10. #define endl        '\n'
  11. #define rep(i,a,b)  for(int i=a;i<b;i++)
  12. #define SIZE        50000
  13. #define watch(x) cout << (#x) << " is " << (x) << endl
  14. using namespace std;
  15.  
  16.  
  17.  
  18. void MOD(ll &x)
  19. {
  20.     if (x >= lol) x -= lol;
  21.     if (x < 0) x += lol;
  22. }
  23.  
  24.  
  25.  
  26. struct segtree
  27. {
  28.     ll maxsubsum;
  29.     ll sum;
  30.     ll maxprefsum;
  31.     ll maxsufsum;
  32. };
  33.                                     //////////////////////////////////////
  34. ll arr[SIZE+5];
  35. segtree tree[4*SIZE+5];     //arr and tree are both 1-indexed//
  36. int n, q;                           //////////////////////////////////////
  37.  
  38.  
  39.  
  40.  
  41. void build(int node, int start, int end)
  42. {
  43.     if(start > end)
  44.         return;
  45.     if(start==end)
  46.     {
  47.         tree[node].maxsubsum = arr[start];
  48.         tree[node].sum = arr[start];
  49.         tree[node].maxprefsum = arr[start];
  50.         tree[node].maxsufsum = arr[start];
  51.     }
  52.     else
  53.     {
  54.         int mid = (start+end)/2;
  55.         build(2*node, start, mid);
  56.         build(2*node+1, mid+1, end);
  57.  
  58.         //tree[node].sum=tree[node].maxprefsum=LLONG_MIN;
  59.         //tree[node].maxsufsum=tree[node].maxsubsum=LLONG_MIN;
  60.  
  61.         tree[node].sum = tree[2*node].sum + tree[2*node+1].sum;
  62.         tree[node].maxprefsum = max(tree[2*node].maxprefsum, tree[2*node].sum + tree[2*node+1].maxprefsum);
  63.         tree[node].maxsufsum = max(tree[2*node+1].maxsufsum, tree[2*node+1].sum + tree[2*node].maxsufsum);
  64.         tree[node].maxsubsum = max(tree[2*node].maxsubsum , max(tree[2*node+1].maxsubsum, tree[2*node].maxsufsum + tree[2*node+1].maxprefsum));         //CHANGES ACCORDING TO QUERY
  65.     }
  66. }
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73. segtree query(int node, int start, int end, int l, int r)
  74. {
  75.     segtree result;
  76.     result.sum=result.maxprefsum= -16000;
  77.     result.maxsufsum=result.maxsubsum= -16000;
  78.     if(start > end || r<start || end<l)        //range of node is completely outside given range
  79.     {
  80.         return result;
  81.     }
  82.     if(l<=start && end<=r)      // range of node is completely inside given range
  83.     {
  84.         return tree[node];
  85.     }
  86.  
  87.     int mid = (start+end)/2;        //range of node is partially inside and partially outside the given range
  88.  
  89.     if (l > mid)
  90.       return query(2*node+1, mid+1, end, l, r);
  91.     if (r <= mid)
  92.       return query(2*node, start, mid, l, r);
  93.  
  94.  
  95.     segtree p1 = query(2*node, start, mid, l, r);
  96.     segtree p2 = query(2*node+1, mid+1, end, l, r);
  97.  
  98.     result.sum = p1.sum + p2.sum;
  99.     result.maxprefsum = max(p1.maxprefsum, p1.sum + p2.maxprefsum);
  100.     result.maxsufsum = max(p2.maxsufsum, p2.sum + p1.maxsufsum);
  101.     result.maxsubsum = max(p1.maxsubsum , max(p2.maxsubsum, p1.maxsufsum + p2.maxprefsum));         //CHANGES ACCORDING TO QUERY
  102.  
  103.     return result;          //CHANGES ACCORDING TO QUERY
  104. }
  105.  
  106.  
  107. void solve()
  108. {
  109.     cin>>n;
  110.     rep(i,1,n+1)
  111.     {
  112.         cin>>arr[i];
  113.         // watch(arr[i]);
  114.     }
  115.     build(1,1,n);
  116.     // cout << " build completed  \n";
  117.     cin>>q;
  118.     // watch(q);
  119.     rep(i,1,q+1)
  120.     {
  121.         int x, y;
  122.         cin>>x>>y;
  123.         // watch(x);
  124.         // watch(y);
  125.         // cout << "query entered\n";
  126.         segtree ans = query(1,1,n,x,y);
  127.         // cout << "query finished\n";
  128.         cout<<ans.maxsubsum<<endl;
  129.     }
  130.  
  131. }
  132.  
  133.  
  134. int main()
  135. {
  136.     ios_base::sync_with_stdio(false);
  137.     cin.tie(0);
  138.     cout.tie(0);
  139.     int t=1;
  140.     // cin>>t;
  141.     while(t--){
  142.         solve();
  143.     }
  144.     return 0;
  145. }
  146.  
Success #stdin #stdout 0s 4340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qcrzqU
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!