fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //typedef long long ll;
  4.  
  5. struct data{
  6. 	int sum, pref, suf, ans;
  7. };
  8.  
  9. data tree[4*50000];
  10.  
  11. data merge(data l, data r){
  12. 	data tmp;
  13. 	tmp.sum = l.sum + r.sum;
  14. 	tmp.pref = max(l.pref , l.sum + r.pref);
  15. 	tmp.suf = max(r.suf , l.suf + r.sum);
  16. 	tmp.ans = max(l.ans, max(r.ans, l.suf+r.pref));
  17. 	return tmp;
  18. }
  19.  
  20. void build(int a[],int v,  int l, int r){
  21. 	if(l == r){
  22. 		tree[v].ans = tree[v].pref = tree[v].suf = tree[v].sum = a[l];
  23. 		return ;
  24. 	}
  25. 	int mid = l + (r-l)/2;
  26. 	build(a, 2*v, l, mid);
  27. 	build(a, 2*v+1, mid+1, r);
  28. 	tree[v] = merge(tree[2*v], tree[2*v+1]);
  29.  
  30. }
  31.  
  32. data query(int v,int cl, int cr, int l, int r){
  33. 	data tmp;
  34. 	if(r<cl || l>cr){
  35. 		tmp.sum = 0;
  36. 		tmp.pref = -999999999;
  37. 		tmp.suf = -999999999;
  38. 		tmp.ans = -999999999;
  39. 		return tmp;
  40. 	}
  41. 	if(l<=cl && cr<=r){
  42. 		return tree[v];
  43. 	}
  44. 	int mid = cl + (cr-cl)/2;
  45. 	if(cl<=l && r<=mid){
  46. 		return query(2*v, cl, mid, l, r);
  47. 	}
  48. 	if(mid+1<=l && r<=cr){
  49. 		return query(2*v+1, mid+1, cr, l, r);
  50. 	}
  51. 	tmp = merge(query(2*v, cl, mid, l, r), query(2*v+1, mid+1, cr, l ,r));
  52. 	return tmp;
  53.  
  54. }
  55.  
  56. int main(void){
  57. 	int n;
  58. 	cin>>n;
  59. 	int a[n];
  60. 	for(int i=0; i<n; i++){
  61. 		cin>>a[i];
  62. 	}
  63. 	build(a, 1, 0, n-1);
  64. 	int m;
  65. 	cin>>m;
  66. 	while(m--){
  67. 		int l, r;
  68. 		cin>>l>>r;
  69. 		l--;
  70. 		r--;
  71. 		data tmp = query(1, 0, n-1, l ,r);
  72. 		cout<<tmp.ans<<endl;
  73. 	}
  74. }
Success #stdin #stdout 0s 4568KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/4Y97gD
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 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!