fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. const int maxn = 50050;
  9. template<class T> inline void sf(T& x) {
  10. 	char c; int mul = 1;
  11. 	while ((c = getchar()) != EOF) {
  12. 		if (c == '-') mul = -1;
  13. 		if(c >= '0' && c <= '9') {
  14. 			x = c-'0'; break;
  15. 		}
  16. 	}
  17. 	if (c == EOF) {
  18.     	x = EOF; return;
  19.     }
  20.     while ((c = getchar())) {
  21.     	if(c >= '0' && c <= '9') {
  22.             x = (x<<1)+(x<<3)+(c-'0');
  23.         }
  24.         else break;
  25.     }
  26.     x *= mul;
  27. }
  28.  
  29. int val[maxn];
  30.  
  31. struct SegNode {
  32. 	int left, right, sum, maxLeft, maxRight, maxAll;
  33.  
  34. 	int mid() {
  35. 		return (left + right) >> 1;
  36. 	}
  37. };
  38.  
  39. struct SegmentTree {
  40.  
  41. 	SegNode tree[maxn*5];
  42.  
  43. 	void pushUp(int idx) {
  44. 		tree[idx].sum = tree[idx<<1].sum + tree[idx<<1|1].sum;
  45. 		tree[idx].maxLeft = max(tree[idx<<1].maxLeft, tree[idx<<1].sum + tree[idx<<1|1].maxLeft);
  46. 		tree[idx].maxRight = max(tree[idx<<1|1].maxRight, tree[idx<<1|1].sum + tree[idx<<1].maxRight);
  47. 		tree[idx].maxAll = max(max(tree[idx<<1].maxAll, tree[idx<<1|1].maxAll), tree[idx<<1].maxRight + tree[idx<<1|1].maxLeft);
  48. 	}
  49.  
  50. 	void build(int left, int right, int idx) {
  51. 		tree[idx].left = left; tree[idx].right = right;
  52. 		if (left == right) {
  53. 			tree[idx].maxAll = tree[idx].maxRight = tree[idx].maxLeft = tree[idx].sum = val[left];
  54. 			return ;
  55. 		}
  56. 		int mid = tree[idx].mid();
  57. 		build(left, mid, idx<<1);
  58. 		build(mid+1, right, idx<<1|1);
  59. 		pushUp(idx);
  60. 	}
  61.  
  62. 	SegNode query(int left, int right, int idx) {
  63. 		if (tree[idx].left >= left && tree[idx].right <= right)
  64. 			return tree[idx];
  65. 		int mid = tree[idx].mid();
  66. 		if (right <= mid) return query(left, right, idx<<1);
  67. 		else if (left > mid) return query(left, right, idx<<1|1);
  68. 		else {
  69. 			SegNode Left = query(left, mid, idx<<1);
  70. 			SegNode Right = query(mid+1, right, idx<<1|1);
  71. 			SegNode result;
  72. 			result.sum = Left.sum + Right.sum;
  73. 			result.maxLeft = max(Left.maxLeft, Left.sum + Right.maxLeft);
  74. 			result.maxRight = max(Right.maxRight, Right.sum + Left.maxRight);
  75. 			result.maxAll = max(max(Left.maxAll, Right.maxAll), Left.maxRight + Right.maxLeft);
  76. 			return result;
  77. 		}
  78. 	}
  79. };
  80. SegmentTree g;
  81.  
  82. int n, q;
  83.  
  84. int main() {
  85. 	sf(n);
  86. 	for (int i = 1; i <= n; i++) 
  87. 		sf(val[i]);
  88. 	scanf("%d", &q); g.build(1, n, 1);
  89. 	for (int i = 0; i < q; i++) {
  90. 		int left, right;
  91. 		sf(left); sf(right);
  92. 		printf("%d\n", g.query(left, right, 1).maxAll);
  93. 	}
  94. }
Success #stdin #stdout 0s 8968KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/5tepgk
SPOJ GSS1
language:
C++ (gcc 8.3)
created:
11 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!