fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. struct node{
  5. 	ll sum,max,psum,ssum;
  6. };
  7. node stree[2000000];
  8. int a[2000000];
  9. int n;
  10. void construct(int l,int r,int p){
  11. 	if(l==r){
  12. 		stree[p].sum=a[l];
  13. 		stree[p].max=a[l];
  14. 		stree[p].psum=a[l];
  15. 		stree[p].ssum=a[l];
  16. 		return;
  17. 	}
  18. 	else{
  19. 		int mid=(l+r)/2;
  20. 		construct(l,mid,2*p+1);
  21. 		construct(mid+1,r,2*p+2);
  22. 	}
  23. 	stree[p].psum=max(stree[2*p+1].psum,stree[2*p+1].sum+stree[2*p+2].psum);
  24. 	stree[p].ssum=max(stree[2*p+2].ssum,stree[2*p+2].sum+stree[2*p+1].ssum);
  25. 	stree[p].sum=stree[2*p+2].sum+stree[2*p+1].sum;
  26. 	stree[p].max=max({stree[p].psum,stree[p].ssum,stree[2*p+1].max,stree[2*p+2].max,stree[2*p+1].ssum+stree[2*p+2].psum});
  27. }
  28. node query(int l,int r,int ql,int qr,int p){
  29. 	if(r>=n||l<0||l>r||ql>r||qr<l){
  30. 		return (node){-100000,-100000,-100000,-100000};
  31. 	}
  32. 	if(qr>=r&&ql<=l){
  33. 		return stree[p];
  34. 	}
  35. 	int mid=(l+r)/2;
  36. 	node left=	query(l,mid,ql,qr,2*p+1);
  37. 	node right=	query(mid+1,r,ql,qr,2*p+2);
  38. 	node mynode;
  39.  
  40.  
  41. 	mynode.sum=left.sum+right.sum;
  42. 	mynode.psum=max(left.psum,left.sum+right.psum);
  43. 	mynode.ssum=max(right.ssum,right.sum+left.ssum);
  44. 	mynode.max=max({left.max,right.max,left.ssum+right.psum,mynode.psum,mynode.ssum});
  45.  
  46. 	return mynode;
  47.  
  48. }
  49.  
  50. int main(){
  51. 	cin>>n;
  52. 	for(int i=0;i<n;i++){
  53. 		cin>>a[i];
  54. 	}
  55. 	construct(0,n-1,0);
  56. 	int m;
  57. 	cin>>m;
  58. 	while(m--){
  59. 		int a,b;
  60. 		cin>>a>>b;
  61. 		node nod=query(0,n-1,a-1,b-1,0);
  62. 		cout<<nod.max<<endl;
  63. 	}
  64.  
  65. 	return 0;
  66. }
Success #stdin #stdout 0s 4360KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/Kk1ari
language:
C++14 (gcc 8.3)
created:
4 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!