fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define SIZE 50000
  6. #define MIN -16000
  7.  
  8. struct Array
  9. {
  10. 	long long int p;
  11. 	long long int s;
  12. 	long long int sub;
  13. 	long long int t;
  14. }tree[5*SIZE];
  15.  
  16. long long int n,a[SIZE];
  17.  
  18. void build(int node, int start, int end)
  19. {
  20. 	if(start==end)
  21. 	{
  22. 		tree[node].p = tree[node].s = tree[node].sub = tree[node].t = a[start];
  23. 	}
  24. 	else
  25. 	{
  26. 		int mid = (start + end)/2;
  27. 		build(2*node, start, mid);
  28. 		build(2*node + 1, mid + 1, end);
  29. 		tree[node].p = max(tree[2*node].t + tree[2*node +1].p, tree[2*node].p);
  30. 		tree[node].s = max(tree[2*node+1].t + tree[2*node].s , tree[2*node+1].s);
  31. 		tree[node].sub = max(max(tree[2*node].sub, tree[2*node + 1].sub), tree[2*node].s+tree[2*node+1].p);
  32. 		tree[node].t = tree[2*node].t + tree[2*node + 1].t;
  33. 	}
  34. }
  35.  
  36. Array query(int node, int start, int end, int l, int r)
  37. {
  38. 	Array a;
  39. 	if(end < l || start > r)
  40. 	{
  41. 		a.p = a.s = a.sub = a.t = MIN;
  42. 		return a;
  43. 	}
  44. 	if(start >= l && end <= r)
  45. 	{
  46. 		return tree[node];
  47. 	}
  48. 	int mid = (start + end)/2;
  49. 	Array p1 = query(2*node, start, mid, l, r);
  50. 	Array p2 = query(2*node +1, mid + 1, end, l, r);
  51. 	if(p1.sub == MIN) return p2;
  52. 	if(p2.sub == MIN) return p1;
  53. 	a.p = max(p1.t + p2.p, p1.p);
  54. 	a.s = max(p2.t + p1.s, p2.s);
  55. 	a.sub = max(max(p1.sub,p2.sub),p1.s + p2.p);
  56. 	a.t = p1.t + p2.t;
  57. 	return a;
  58. }
  59.  
  60. int main()
  61. {
  62. 	scanf("%lld",&n);
  63. 	for(int i=0;i<n;++i)
  64. 		scanf("%lld",&a[i]);
  65. 	build(1,0,n-1);
  66. 	int m;
  67. 	scanf("%d",&m);
  68. 	while(m--)
  69. 	{
  70. 		int l,r;
  71. 		scanf("%d %d",&l,&r);
  72. 		long long int result=query(1,0,n-1,l-1,r-1).sub;
  73. 		cout<<result<<endl;
  74. 	}
  75. 	return 0;
  76. }
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/K6sJtW
language:
C++ (gcc 8.3)
created:
5 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!