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. void construct(int l,int r,int p){
  10. 	if(l==r){
  11. 		stree[p].sum=a[l];
  12. 		stree[p].max=a[l];
  13. 		stree[p].psum=a[l];
  14. 		stree[p].ssum=a[l];
  15. 		return;
  16. 	}
  17. 	else{
  18. 		int mid=(l+r)/2;
  19. 		construct(l,mid,2*p+1);
  20. 		construct(mid+1,r,2*p+2);
  21. 	}
  22. 	stree[p].psum=max(stree[2*p+1].psum,stree[2*p+1].sum+stree[2*p+2].psum);
  23. 	stree[p].ssum=max(stree[2*p+2].ssum,stree[2*p+2].sum+stree[2*p+1].ssum);
  24. 	stree[p].ssum=stree[2*p+2].sum+stree[2*p+1].sum;
  25. 	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});
  26. }
  27. node query(int l,int r,int ql,int qr,int p){
  28. 	if(qr<l||ql>r){
  29. 		return (node){-100000,-100000,-100000,-100000};
  30. 	}
  31. 	if(qr<=r&&ql>=l){
  32. 		return stree[p];
  33. 	}
  34. 	int mid=(l+r)/2;
  35. 	node left=	query(l,mid,ql,qr,2*p+1);
  36. 	node right=	query(mid+1,r,ql,qr,2*p+2);
  37. 	node mynode;
  38.  
  39. 	mynode.sum=left.sum+right.sum;
  40. 	mynode.psum=max(left.psum,left.sum+right.psum);
  41. 	mynode.ssum=max(right.ssum,right.sum+left.ssum);
  42. 	mynode.max=max({left.max,right.max,left.ssum+right.psum});
  43.  
  44. 	return mynode;
  45.  
  46. }
  47.  
  48. int main(){
  49. 	ll n;
  50. 	cin>>n;
  51. 	for(int i=0;i<n;i++){
  52. 		cin>>a[i];
  53. 	}
  54. 	construct(0,n-1,0);
  55. 	int m;
  56. 	cin>>m;
  57. 	while(m--){
  58. 		int a,b;
  59. 		cin>>a>>b;
  60. 		node nod=query(0,n-1,a,b,0);
  61. 		cout<<nod.max<<endl;
  62. 	}
  63.  
  64. 	return 0;
  65. }
Time limit exceeded #stdin #stdout 5s 4384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/D3Z4QN
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!