fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 5;
  5.  
  6. int n , m , l;
  7. long long a[N];
  8.  
  9. struct node {
  10. 	int lef;
  11. 	int righ;
  12. 	int ans;
  13. 	node() {
  14. 		lef = 0;
  15. 		righ = 0;
  16. 		ans = 0;
  17. 	}
  18. };
  19.  
  20. node get_new_node() {
  21. 	return node();
  22. }
  23.  
  24. node segtree[N << 2];
  25.  
  26. node merges(node a , node b) {
  27. 	node res = node();
  28. 	res.lef = a.lef;
  29. 	res.righ = b.righ;
  30. 	if(a.righ == 1 and b.lef == 1) {
  31. 		res.ans = a.ans + b.ans - 1;
  32. 	} else {
  33. 		res.ans = a.ans + b.ans;
  34. 	}
  35. 	return res; 
  36. }
  37.  
  38.  
  39. void upd(int node , int u , int v , int idx) {
  40. 	if(u > v or u > idx or v < idx) return;
  41. 	if(u >= idx and v <= idx) {
  42. 		segtree[node].lef = 1;
  43. 		segtree[node].righ = 1;
  44. 		segtree[node].ans = 1;
  45. 		return;
  46. 	}
  47. 	int m = (u + v) / 2;
  48. 	upd(node * 2 , u , m , idx);
  49. 	upd(1 + (node * 2) , m + 1 , v , idx);
  50. 	segtree[node] = merges(segtree[node * 2] , segtree[1 + (node * 2)]);
  51. }
  52.  
  53. node query(int node , int u , int v , int l , int r) {
  54. 	if(u > v or u > r or v < l) {
  55. 		return get_new_node();
  56. 	}
  57. 	if(u >= l and v <= r) {
  58. 		return segtree[node];
  59. 	}
  60. 	int m = (u + v) / 2;
  61. 	return merges(query(node * 2 , u , m , l , r) , query(1 + (node * 2) , m + 1 , v , l , r));
  62. }
  63.  
  64.  
  65. void solve() {
  66. 	for(int i = 0; i < N << 2; ++i) segtree[i] = node();
  67. 	scanf("%d%d%d" , &n, &m, &l);
  68. 	for(int i = 1; i <= n; ++i) scanf("%lld", a + i);
  69. 	for(int i = 1; i <= n; ++i) {
  70. 		if(a[i] > l) {
  71. 			upd(1 , 1 , n , i);
  72. 		}
  73. 	}
  74. 	while(m--) {
  75. 		int typ; scanf("%d", &typ);
  76. 		if(!typ) {
  77. 			printf("%d\n" , query(1 , 1 , n , 1 , n).ans);
  78. 		} else {
  79. 			int p, d; scanf("%d%d" , &p, &d);
  80. 			if(a[p] <= l) {
  81. 				a[p] += d;
  82. 				if(a[p] > l) {
  83. 					upd(1 , 1 , n , p);
  84. 				}
  85. 			}
  86. 		}
  87. 	}
  88. }
  89.  
  90. int main() {
  91. 	solve();
  92. 	return 0;
  93. }
Success #stdin #stdout 0s 20704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/x0wzkB
language:
C++14 (gcc 8.3)
created:
5 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!