fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<string.h>
  3. using namespace std;
  4. #define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  5. #define int long long int
  6. #define fi first
  7. #define se second
  8. #define pub push_back
  9. #define mkp make_pair
  10. #define pi pair<int,int>
  11. #define all(v) (v).begin(), (v).end()
  12. #define rep(i, l, r) for(int i=(int)(l);i<(int)(r);i++)
  13. #define repd(i, l, r) for (int i=(int)(l);i>=(int)(r);i--)
  14. int power(int x, unsigned int y){int res = 1;while (y > 0){ if (y & 1){res = res*x;} y = y>>1;x = x*x;}return res;}
  15. int powermod(int x, unsigned int y, int p){int res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1; x = (x*x) % p;}return res;}
  16. #define print2d(mat,n,m){for(int i=0;i<(int)(n);i++){for(int j=0;j<(m);j++){cout<<mat[i][j]<<" "<< "endl"[j == m];}}}
  17. #define print1d(mat,n){for(int i=0;i<(int)(n);i++)cout<<mat[i]<<" ";cout<<endl;}
  18. #define clr(a,x) memset(a,x,sizeof(a))
  19. #define rr(v) for(auto &val:v)
  20. #define print(v) for (const auto itr:v){cout<<itr<<' ';}cout<<endl;
  21. #define init(v,x) for (auto &itr:v){itr=x;}
  22. #define minpq(x) x,vector<x>,greater<x>
  23. #define ln length()
  24. #define sz size()
  25. #define inf 1e18;
  26. int a[100005],n,q,a1,b;
  27. struct val{
  28. int ps;
  29. int ss;
  30. int ms;
  31. int su;
  32. };
  33. struct val tree[4*100005];
  34. void build(int node,int start,int en)
  35. {
  36.   //  cout<<node<<endl;
  37.     if (start==en)
  38.     {
  39.         tree[node].ps=a[start];
  40.         tree[node].ss=a[start];
  41.         tree[node].ms=a[start];
  42.         tree[node].su=a[start];
  43.     }
  44.     else
  45.     {
  46.         int mid=(start+en)/2;
  47.         build(2*node,start,mid);
  48.         build(2*node+1,mid+1,en);
  49.         tree[node].su=tree[2*node].su+tree[2*node+1].su;
  50.         tree[node].ps=max(tree[2*node].ps,tree[2*node].su+tree[2*node+1].ps);
  51.         tree[node].ss=max(tree[2*node+1].ss,tree[2*node+1].su+tree[2*node].ss);
  52.         tree[node].ms=max(tree[node].ps,max(tree[node].ss,max(tree[node].su,max(tree[2*node].ms,max(tree[2*node+1].ms,tree[2*node].ss+tree[2*node+1].ps)))));
  53.  
  54.     }
  55. }
  56. struct val query(int node,int start, int en , int l, int r)
  57. {
  58.   //#  cout<<node<<" "<<start<<" "<<en<<" "<<l<<" "<<r<<endl;
  59.     if (r<start || l>en)
  60.     {
  61.         struct val mi;
  62.         mi.ps=-inf;mi.ss=-inf;mi.ms=-inf;mi.su=-inf;
  63.         return mi ;
  64.     }
  65.     if(l<=start && r>=en)
  66.     {
  67.         return tree[node];
  68.     }
  69.     else
  70.     {
  71.  
  72.         int mid=(start+en)/2;
  73.         struct val q1=query(2*node,start,mid,l,r);
  74.         struct val q2=query(2*node+1,mid+1,en,l,r);
  75.         struct val an;
  76.         an.su=q1.su+q2.su;
  77.         an.ps=max(q1.ps,q1.su+q2.ps);
  78.         an.ss=max(q2.ss,q2.su+q1.ss);
  79.         an.ms=max(an.ps,max(an.ss,max(an.su,max(q1.ms,max(q2.ms,q1.ss+q2.ps)))));
  80.         return an;
  81.     }
  82. }
  83. main()
  84. {
  85.     cin>>n;
  86.     rep(i,0,n)
  87.     {
  88.         cin>>a[i];
  89.     }
  90.     cin>>q;
  91.     build(1,0,n-1);
  92.    // print1d(tree,8)
  93.     rep(i,0,q)
  94.     {
  95.         cin>>a1>>b;
  96.         cout<<query(1,0,n-1,a1-1,b-1).ms<<endl;
  97.     }
  98.  
  99.  
  100. }
  101.  
Success #stdin #stdout 0s 4272KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/3YTYsG
problem GSS1, based on SPOJ submission 24303732 (CPP14), 2019-08-27 11:28:19
language:
C++14 (gcc 8.3)
created:
4 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!