fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 2e5 + 5; 
  11.  
  12. int n, q; 
  13. int a[N];  
  14.  
  15. struct node {
  16. 	ll ans, max_suf, max_pref, sum;  
  17.  
  18. 	node() {}
  19.  
  20. 	node(ll x) {
  21. 		ans = max_suf = max_pref = max(0ll, x);   
  22. 		sum = x;  
  23. 	}
  24. }; 
  25.  
  26. node operator+(const node& a, const node& b) {
  27. 	node c; 
  28. 	c.ans = max({a.ans, b.ans, a.max_suf + b.max_pref});
  29. 	c.max_suf = max(b.max_suf, b.sum + a.max_suf);   
  30. 	c.max_pref = max(a.max_pref, a.sum + b.max_pref); 
  31. 	c.sum = a.sum + b.sum; 
  32. 	return c;   
  33. }
  34.  
  35. node seg[4 * N]; 
  36.  
  37. void build(int id, int l, int r) {
  38. 	if (l == r) {
  39. 		seg[id] = node(a[l]); 
  40. 		return; 
  41. 	}
  42. 	int mid = (l + r) >> 1; 
  43. 	build(id * 2, l, mid); 
  44. 	build(id * 2 + 1, mid + 1, r); 
  45. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  46. }
  47.  
  48. void update(int id, int l, int r, int pos, int val) {
  49. 	if (l > pos || r < pos) return; 
  50.  
  51. 	if (l == r) {
  52. 		seg[id] = node(val); 
  53. 		return;
  54. 	}
  55.  
  56. 	int mid = (l + r) >> 1; 
  57. 	update(id * 2, l, mid, pos, val); 
  58. 	update(id * 2 + 1, mid + 1, r, pos, val); 
  59.  
  60. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  61. }
  62.  
  63. int main() {
  64. 	ios::sync_with_stdio(0); cin.tie(0);  	
  65. 	cin >> n >> q;  
  66. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  67.  
  68. 	build(1, 1, n); 
  69.  
  70. 	while (q--) {
  71. 		int pos, val; 
  72. 		cin >> pos >> val; 
  73. 		update(1, 1, n, pos, val); 
  74. 		cout << seg[1].ans << '\n'; 
  75. 	}
  76. }
Success #stdin #stdout 0.01s 5568KB
comments (?)
stdin
copy 
5 3
1 2 -3 5 -1
2 6
3 1
2 -2
stdout
copy 
9
13
6
https://ideone.com/hlRmYp
language:
C++14 (gcc 8.3)
created:
1 year 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!