fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<map>
  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 F           first
  10. #define S           second
  11. #define sz(x)       (int)x.size()
  12. #define hell        1000000007
  13. #define endl        '\n'
  14. #define rep(i,a,b)  for(int i=a;i<b;i++)
  15. #define rep1(i,a,b) for(ll i=a;i<= b;i++)
  16. #define PI          3.14159
  17. #define MAX         1000001
  18. //sconst ll maxn = (ll)1e18;
  19. using namespace std;
  20. struct node
  21. {
  22.   ll sum = LLONG_MIN;
  23.   ll bestleftsum = LLONG_MIN;
  24.   ll bestrightsum = LLONG_MIN;
  25.   ll maxsum = LLONG_MIN;
  26.   ll maxvalue = LLONG_MIN;
  27. };
  28. node tree[500005];
  29. ll arr[100005];
  30. void buildtree(ll start,ll end,ll treenode,ll *arr)
  31. {
  32.   if(start == end)
  33.   {
  34.     tree[treenode].maxsum = tree[treenode].sum = tree[treenode].bestleftsum = tree[treenode].bestrightsum = tree[treenode].maxvalue = arr[start];
  35.     return;
  36.   }
  37.   ll mid = (start + end)/2;
  38.   buildtree(start,mid,2*treenode,arr);
  39.   buildtree(mid+1,end,2*treenode + 1,arr);
  40.   node left = tree[2*treenode];
  41.   node right = tree[2*treenode + 1];
  42.   tree[treenode].sum = left.sum + right.sum;
  43.   tree[treenode].bestleftsum = max(left.sum + right.bestleftsum,left.bestrightsum);
  44.   tree[treenode].bestrightsum = max(right.sum + left.bestrightsum,right.bestleftsum);
  45.   tree[treenode].maxsum = max(max(left.maxsum,right.maxsum),left.bestrightsum + right.bestleftsum);
  46.   tree[treenode].maxvalue = max(tree[treenode].sum,max(tree[treenode].bestleftsum,max(tree[treenode].bestrightsum,max(tree[treenode].maxsum,max(left.maxvalue,right.maxvalue)))));
  47.   return;
  48. }
  49. void updateArray(ll *arr,ll start,ll end,ll treenode,ll idx,ll value)
  50. {
  51.   if(start == end)
  52.   {
  53.     tree[treenode].maxsum = tree[treenode].sum = tree[treenode].bestleftsum = tree[treenode].bestrightsum = tree[treenode].maxvalue = value;
  54.     return;
  55.   }
  56.   ll mid = start + (end - start)/2;
  57.   if(idx > mid)
  58.   {
  59.     updateArray(arr,mid + 1,end,2*treenode + 1,idx,value);
  60.   }
  61.   if(idx <= mid)
  62.   {
  63.     updateArray(arr,start,mid,2*treenode,idx,value);
  64.   }
  65.   node left = tree[2*treenode];
  66.   node right = tree[2*treenode + 1];
  67.   tree[treenode].sum = left.sum + right.sum;
  68.   tree[treenode].bestleftsum = max(left.sum + right.bestleftsum,left.bestrightsum);
  69.   tree[treenode].bestrightsum = max(right.sum + left.bestrightsum,right.bestleftsum);
  70.   tree[treenode].maxsum = max(max(left.maxsum,right.maxsum),left.bestrightsum + right.bestleftsum);
  71.   tree[treenode].maxvalue = max(tree[treenode].sum,max(tree[treenode].bestleftsum,max(tree[treenode].bestrightsum,max(tree[treenode].maxsum,max(left.maxvalue,right.maxvalue)))));
  72.   return;
  73. }
  74. node query(ll* arr,ll start,ll end,ll treenode,ll idx1,ll idx2)
  75. {
  76.   node result;
  77.   result.sum = result.bestrightsum = result.bestleftsum = result.maxsum = LLONG_MIN;
  78.   if(start >= idx1 && end <= idx2)
  79.   {
  80.     return tree[treenode];
  81.   }
  82.   if(start > idx2 || end < idx1)
  83.   {
  84.     return result;
  85.   }
  86.   ll mid = (start + end)/2;
  87.   node left = query(arr,start,mid,2*treenode,idx1,idx2);
  88.   node right = query(arr,mid+1,end,2*treenode+1,idx1,idx2);
  89.   result.sum = left.sum + right.sum;
  90.   result.bestleftsum = max(left.sum + right.bestleftsum,left.bestrightsum);
  91.   result.bestrightsum = max(right.sum + left.bestrightsum,right.bestleftsum);
  92.   result.maxsum = max(max(left.maxsum,right.maxsum),left.bestrightsum + right.bestleftsum);
  93.   result.maxvalue = max(tree[treenode].sum,max(tree[treenode].bestleftsum,max(tree[treenode].bestrightsum,max(tree[treenode].maxsum,max(left.maxvalue,right.maxvalue)))));
  94.   return result;
  95. }
  96. int main()
  97. {
  98.   ios_base::sync_with_stdio(false);
  99.     cin.tie(0);
  100.     cout.tie(0);
  101.     memset(tree,0,sizeof(tree));
  102.     ll n,q;
  103.     cin >> n ;
  104.     for(ll i = 1; i <= n; i++)
  105.     {
  106.       cin >> arr[i];
  107.     }
  108.     cin >> q;
  109.     buildtree(1,n,1,arr);
  110.     for(ll i = 0; i < q; i++)
  111.     {
  112.       ll num1,num2;
  113.       cin >> num1 >> num2;
  114.       cout << query(arr,1,n,1,num1,num2).maxsum << endl;
  115.     }
  116.     return 0;
  117. }
Time limit exceeded #stdin #stdout 5s 22300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2Be61Z
language:
C++14 (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!