fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define 		ll long long
  5. #define         max3(a, b, c) max(max(a, b), c)
  6. struct tre
  7. {
  8. 	ll suf,pref,seg,sum;
  9. };
  10. vector<tre>tree(400001);
  11. tre merge(tre a,tre b)
  12. {
  13. 	tre t={max(b.suf,b.sum+a.suf),max(a.pref,a.sum+b.pref),max3(a.seg,b.seg,a.suf+b.pref),a.sum+b.sum};
  14. 	return t;
  15. }
  16. void build_tree(ll int *a, ll int s,ll int e, ll int index)
  17. {
  18. 	if(s==e)
  19. 	{
  20. 		if(a[s]>0)
  21. 		tree[index] = {a[s],a[s],a[s],a[s]};
  22. 		else
  23. 		tree[index] = {0,0,0,a[s]};
  24. 		return;
  25. 	}
  26. 	ll int mid = (s+e)/2;
  27. 	build_tree(a,s,mid,2*index);
  28. 	build_tree(a,mid+1,e,2*index+1);
  29. 	tree[index] = merge(tree[2*index],tree[2*index+1]);
  30. 	return;
  31. }
  32.  
  33. //point update
  34. void point_update(ll int ss,ll int se, ll i,ll int inc,ll int index)
  35. {
  36. 	if(i>se || i<ss)
  37. 	return;
  38. 	if(ss == se)
  39. 	{
  40. 		if(inc>0)
  41. 		tree[index] = {inc,inc,inc,inc};
  42. 		else
  43. 		tree[index] = {0,0,0,inc};
  44. 		return;
  45. 	}
  46. 	ll int mid = (ss + se)/2;
  47. 	point_update(ss,mid,i,inc,2*index);
  48. 	point_update(mid+1,se,i,inc,2*index+1);
  49. 	tree[index] = merge(tree[2*index],tree[2*index+1]);
  50. 	return;
  51. }
  52.  
  53.  
  54.  
  55. void solve()
  56. {
  57. 	int n,q;
  58. 	cin>>n>>q;
  59.  
  60. 	ll a[n];
  61. 	for(int i=0;i<n;i++)
  62. 	cin>>a[i];
  63.  
  64. 	build_tree(a,0,n-1,1);
  65. 	// for(int i=1;i<=4*n;i++)
  66. 	// cout<<tree[i]<<endl;
  67. 	cout<<tree[1].seg<<endl;
  68.  
  69. 	while(q--)
  70. 	{
  71. 		ll num,l;
  72. 		cin>>num>>l;
  73. 		point_update(0,n-1,num,l,1);
  74. 		cout<<tree[1].seg<<endl;
  75. 		a[num] = l;
  76. 	}
  77.  
  78. }
  79. int main()
  80. {
  81. 	ios_base::sync_with_stdio(false); 
  82.     	cin.tie(NULL); 
  83.  
  84.     // int src[101]={0};
  85.     // int dest[101]={0};
  86.  
  87.     ll int t=1;
  88. 	 // cin>>t;
  89. 	while(t--)
  90. 	{  
  91.       solve();
  92.     }
  93.  
  94. 	return 0;
  95. }
  96.  
Runtime error #stdin #stdout 0.01s 15896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xIO4Qm
language:
C++14 (clang 8.0)
created:
3 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!