fork(2) download 
  1. #include<stdio.h>
  2. #include<map>
  3.  
  4. #define min -9999999
  5.  
  6. using namespace std;
  7.  
  8. struct node
  9. {
  10. 	long best, lsum, rsum, total;
  11. };
  12.  
  13. map<long, node>segtree;
  14. map<long, long>a;
  15.  
  16. long maxfun(long pg, long ss)
  17. {
  18. 	return pg>ss?pg:ss;
  19. }
  20.  
  21. void pg(long pos)
  22. {
  23. 	segtree[pos].total = segtree[2*pos+1].total + segtree[2*pos+2].total;
  24. 	segtree[pos].lsum = maxfun(segtree[2*pos + 1].lsum, segtree[2*pos + 1].total + segtree[2*pos+2].lsum);
  25. 	segtree[pos].rsum = maxfun(segtree[2*pos + 2].rsum, segtree[2*pos + 2].total + segtree[2*pos+1].rsum);
  26. 	segtree[pos].best = maxfun(maxfun(segtree[2*pos+1].best, segtree[2*pos+2].best), segtree[2*pos+1].rsum + segtree[2*pos+2].lsum);
  27. }
  28.  
  29. void construct(long lo, long hi, long pos)
  30. {
  31. 	if(lo == hi)
  32. 	{
  33. 		segtree[pos].best = a[lo];
  34. 		segtree[pos].lsum = a[lo];
  35. 		segtree[pos].rsum = a[lo];
  36. 		segtree[pos].total = a[lo];
  37.  
  38. 		return;
  39. 	}
  40.  
  41. 	long mid = lo + (hi - lo)/2;
  42.  
  43. 	construct(lo, mid, 2*pos+1);
  44. 	construct(mid+1, hi, 2*pos+2);
  45.  
  46. 	pg(pos);
  47. }
  48.  
  49. node query(long qlo, long qhi, long lo, long hi, long pos)
  50. {
  51. 	if(qlo>hi || qhi<lo)
  52. 	{
  53. 		return (node)
  54. 		{
  55. 			0, 
  56. 			0, 
  57. 			0, 
  58. 			0
  59. 		};//return something empty
  60. 	}
  61.  
  62. 	if(qlo<=lo && qhi>=hi)
  63. 	{
  64. 		//res = segtree[pos].best;
  65. 		return segtree[pos];
  66. 	}
  67.  
  68. 	long mid = lo + (hi - lo)/2;
  69.  
  70. 	node left = query(qlo, qhi, lo, mid, 2*pos+1), right = query(qlo, qhi, mid+1, hi, 2*pos+2), pr;
  71.  
  72. 	pr.best = maxfun(maxfun(left.rsum+right.total, left.total + right.lsum),maxfun(left.best, right.best));
  73. 	pr.lsum = maxfun(left.lsum, left.total + right.lsum);
  74. 	pr.rsum = maxfun(left.rsum + right.total, right.rsum);
  75. 	pr.total = left.total + right.total;
  76.  
  77. 	return pr;
  78.  
  79. }
  80.  
  81.  
  82. int main()
  83. {
  84.  
  85. 	//freopen("C:\\Users\\Shraeyas\\Documents\\pg\\pr_ag\\prag_gss1.txt", "r", stdin);
  86.  
  87. 	long n;
  88. 	scanf("%ld", &n);
  89.  
  90. 	for(long i=0;i<n;i++)
  91. 	{
  92. 		scanf("%ld", &a[i]);
  93. 	}
  94.  
  95. 	construct(0, n-1, 0);
  96.  
  97. 	long q;
  98. 	scanf("%ld", &q);
  99.  
  100. 	while(q--)
  101. 	{
  102. 		long x,y;
  103. 		scanf("%ld %ld", &x, &y);
  104. 		x--, y--;
  105.  
  106. 		node pra = query(x, y, 0, n-1, 0);
  107.  
  108. 		printf("%ld\n", maxfun(maxfun(pra.lsum, pra.rsum), maxfun(pra.total, pra.best)));
  109. 	}
  110. }
  111.  
Success #stdin #stdout 0s 15248KB
comments ()
stdin 
6
1 -2 3 4 -1 6
6
1 3
2 6
1 6
4 6
5 6
3 5
stdout 
3
12
12
9
6
7
https://ideone.com/Ft3cag
language:
C++14 (gcc 8.3)
created:
8 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!