fork download 
  1. #include <iostream>
  2. #include <climits>
  3.  
  4. #define forn(i,a,b) for(int i = a; i < b; i++)
  5. #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define MAX 1310740
  7. #define M INT_MIN
  8.  
  9. using namespace std;
  10.  
  11. struct node
  12. {
  13.     long long int prefix{0};
  14.     long long int suffix{0};
  15.     long long int sum{0};
  16.     long long int best{0};
  17. public:
  18.     node() = default;
  19.     node(long long n)
  20.     {
  21.         prefix = suffix = sum = best = n;
  22.     }
  23.     node& operator=(long long n)
  24.     {
  25.         prefix = suffix = sum = best = n;
  26.         return *this;
  27.     }
  28.     friend ostream& operator<<(ostream&, const node&);
  29. } tree[MAX];
  30.  
  31. ostream& operator<<(ostream& out, const node& nd)
  32. {
  33.     out << "prefix: " << nd.prefix << endl;
  34.     out << "suffix: " << nd.suffix << endl;
  35.     out << "sum: " << nd.sum << endl;
  36.     out << "best: " << nd.best << endl;
  37.     return out;
  38. }
  39.  
  40. void constructST(int arr[], int ss, int se, int si)
  41. {
  42.     if(ss > se) return;
  43.     if(ss == se)
  44.     {
  45.         tree[si] = arr[ss];
  46.         return;
  47.     }
  48.     int mid = ss + (se-ss)/2;
  49.     constructST(arr, ss, mid, 2*si+1);
  50.     constructST(arr, mid+1, se, 2*si+2);
  51.     tree[si].best = tree[2*si+1].suffix + tree[2*si+2].prefix;
  52.     tree[si].prefix = max(tree[2*si+1].prefix, tree[2*si+2].prefix + tree[2*si+1].sum);
  53.     tree[si].suffix = max(tree[2*si+2].suffix, tree[2*si+2].sum + tree[2*si+1].suffix);
  54.     tree[si].sum = tree[2*si+1].sum+tree[2*si+2].sum;
  55.     if(tree[2*si+1].best > tree[si].best)
  56.     {
  57.         tree[si].best = tree[2*si+1].best;
  58.     }
  59.     else if(tree[2*si+2].best > tree[si].best)
  60.     {
  61.         tree[si].best = tree[2*si+2].best;
  62.     }
  63.     return;
  64. }
  65.  
  66. node getmax(int qs, int qe, int ss, int se, int si, int n)
  67. {
  68.     //cout << "present index: " << si << endl;
  69.     if(ss > qe || se < qs || qs > qe) return node(M);
  70.     //cout << ss << " " << se << "\n" << tree[si] << endl;
  71.  
  72.     if(ss >= qs && se <= qe) return tree[si];
  73.  
  74.     int mid = ss + (se-ss)/2;
  75.  
  76.     node left = getmax(qs,qe,ss,mid,2*si+1,n);
  77.     node right = getmax(qs,qe,mid+1,se,2*si+2,n);
  78.  
  79.     if(left.best == M) return right;
  80.     else if(right.best == M) return left;
  81.  
  82.     node ans(M);
  83.  
  84.     ans.best = max(left.best, right.best);
  85.     ans.best = max(ans.best, left.suffix + right.prefix);
  86.     ans.prefix = max(left.prefix, left.sum+right.prefix);
  87.     ans.suffix = max(right.suffix, right.sum+left.suffix);
  88.     ans.sum = left.sum+right.sum;
  89. //    if(si == 0)
  90. //    {
  91. //        cout << left << "\n" << right << "\n" << ans;
  92. //    }
  93.     return ans;
  94. }
  95.  
  96. int main()
  97. {
  98.     boost;
  99.     int n;
  100.     cin >> n;
  101.     int arr[n];
  102.     forn(i,0,n)
  103.     {
  104.         cin >> arr[i];
  105.     }
  106.     constructST(arr,0,n-1,0);
  107.     int m;
  108.     cin >> m;
  109.     while(m--)
  110.     {
  111.         int l, r;
  112.         cin >> l >> r;
  113.         l--;r--;
  114.         cout << getmax(l,r,0,n-1,0,n).best << endl;
  115.     }
  116. }
  117.  
Success #stdin #stdout 0s 4552KB
comments (?)
stdin 
3 
-1 2 3
1
1 2
stdout 
2
https://ideone.com/CERlQ9
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!