fork download
copy 
  1. #include<bits\stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. #define endl "\n"
  6.  
  7.  
  8. struct node
  9. {
  10. 	int mn = 1e9 + 7;
  11. 	node(int x = 0)
  12. 	{
  13. 		mn = x;
  14. 	}
  15.  
  16. };
  17. node out()
  18. {
  19. 	return node(1e9 + 7);
  20. }
  21. node proces(node a, node b)
  22. {
  23. 	node c;
  24. 	c.mn = min(a.mn, b.mn);
  25. 	return c;
  26. }
  27. int const nn = 4e5 + 1;
  28. int n;
  29. int a[nn];
  30. node tree[nn];
  31. int ans = 0;
  32. void build_tree(int s, int e, int ind)
  33. {
  34. 	if (s == e)
  35. 	{
  36. 		tree[ind] = node(a[s]);
  37. 		return;
  38. 	}
  39. 	int mid = (s + e) / 2;
  40. 	build_tree(s, mid, ind * 2);
  41. 	build_tree(mid + 1, e, (ind * 2) + 1);
  42. 	tree[ind] = proces(tree[ind * 2], tree[(ind * 2) + 1]);
  43. 	return;
  44. }
  45. void query(int ss, int se, int qs, int qe, int ind, int p)
  46. {
  47. 	//complete overlap
  48. 	if (ss >= qs && se <= qe)
  49. 		if (tree[ind].mn > p)
  50. 			return;
  51.  
  52. 	// no overlap
  53. 	if (qe<ss || qs>se)
  54. 		return;
  55.  
  56. 	if (ss == se)
  57. 	{
  58. 		ans++;
  59. 		tree[ind].mn = 1e9 + 7;
  60. 		return;
  61. 	}
  62.  
  63. 	int mid = (ss + se) / 2;
  64. 	 query(ss, mid, qs, qe, ind * 2, p);
  65. 	 query(mid + 1, se, qs, qe, ind * 2 + 1, p);
  66. 	 tree[ind].mn = min(tree[ind * 2].mn, tree[ind * 2 + 1].mn);
  67. 	 return;
  68. }
  69. void update(int ss, int se, int i, int new_val, int ind)
  70.  
  71. {
  72. 	//case where the I is out of bound 
  73. 	if (i > se || i < ss)
  74. 		return;
  75.  
  76. 	// leaf node 
  77. 	if (ss == se)
  78. 	{
  79. 		tree[ind] = node(new_val);
  80. 		return;
  81. 	}
  82. 	//otherwise 
  83. 	int mid = (ss + se) / 2;
  84. 	update(ss, mid, i, new_val, ind * 2);
  85. 	update(mid + 1, se, i, new_val, ind * 2 + 1);
  86.  
  87. 	tree[ind] = proces(tree[ind * 2], tree[ind * 2 + 1]);
  88. 	return;
  89. }
  90. void fast()
  91. {
  92. 	ios_base::sync_with_stdio(0);
  93. 	cin.tie(0);
  94. 	cout.tie(0);
  95. }
  96. int32_t main()
  97. {
  98. 	fast();
  99. 	int n, m;
  100. 	cin >> n >> m;
  101.  
  102. 	for (int i = 1; i <= n; i++)
  103. 		a[i] = 1e9 + 7;
  104.  
  105. 	build_tree(1, n, 1);
  106. 	while (m--)
  107. 	{
  108. 		int ty;
  109. 		cin >> ty;
  110. 		if (ty == 1)
  111. 		{
  112. 			int ind, h;
  113. 			cin >> ind >> h;
  114. 			ind++;
  115. 			update(1, n, ind, h, 1);
  116. 		}
  117. 		else
  118. 		{
  119. 			int l, r, p;
  120. 			cin >> l >> r >> p;
  121. 			l++;
  122. 			ans = 0;
  123. 			query(1, n, l, r, 1, p);
  124. 			cout << ans << endl;
  125. 		}
  126.  
  127. 	}
  128. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1:9: fatal error: bits\stdc++.h: No such file or directory
 #include<bits\stdc++.h>
         ^~~~~~~~~~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/vuufhC
language:
C++14 (gcc 8.3)
created:
341 days 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!