fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. #define min(x, y) ((x) < (y) ? (x) : (y))
  7. #define max(x, y) ((x) > (y) ? (x) : (y))
  8.  
  9. pair<int, int> t[999999];
  10. int N, a[40000], query;
  11.  
  12. void build(int v, int tl, int tr, int num) {
  13. 	if (tl == tr){
  14. 		t[v].first = a[tl] > num ? 1 : 0;
  15. 		t[v].second = a[tl];
  16. 	}
  17. 	else {
  18. 		int tm = (tl + tr) / 2;
  19. 		build(v * 2, tl, tm, num);
  20. 		build(v * 2 + 1, tm + 1, tr, num);
  21. 		t[v].first = t[v * 2].first + t[v * 2 + 1].first;
  22. 		t[v].second = max(t[v * 2].second, t[v * 2 + 1].second);
  23. 	}
  24. }
  25.  
  26.  
  27. int sum(int v, int tl, int tr, int l, int r) {
  28. 	if (l > r)
  29. 		return 0;
  30. 	if (l == tl && r == tr)
  31. 		return t[v].first;
  32. 	int tm = (tl + tr) / 2;
  33. 	return sum(v * 2, tl, tm, l, min(r, tm)) + sum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
  34. }
  35.  
  36. void update (int v, int tl, int tr, int pos_1, int pos_2, int new_val) {
  37. 	if (tl == tr){
  38. 		if (t[v].second > new_val)
  39. 			t[v].first = 1;
  40. 		else
  41. 			t[v].first = 0;
  42. 	}
  43. 	else {
  44. 		int tm = (tl + tr) / 2;
  45. 		if (pos_1 <= tm && pos_2 <= tm)
  46. 			update (v * 2, tl, tm, pos_1, pos_2, new_val);
  47. 		else if (pos_1 <= tm && pos_2 > tm){
  48. 			update (v * 2, tl, tm, pos_1, tm, new_val);
  49. 		}
  50. 		else if (pos_1 > tm && pos_2 > tm)
  51. 			update (v * 2 + 1, tm + 1, tr, pos_1, pos_2, new_val);
  52. 		t[v].first = t[v * 2].first + t[v * 2 + 1].first;
  53. 		t[v].second = max(t[v * 2].second, t[v * 2 + 1].second);
  54. 	}
  55. }
  56.  
  57. int main(){
  58. 	cin >> N;
  59. 	for (int i = 0; i < N; i++)
  60. 		cin >> N;
  61.  
  62. 	build(1, 0, N - 1, 0);
  63.  
  64. 	cin >> query;
  65.  
  66. 	for (int i = 0; i < query; i++){
  67. 		int x, y, z;
  68. 		cin >> x >> y >> z;
  69. 		update(1, 0, N - 1, x - 1, y- 1, z);
  70. 		cout << sum(1, 0, N - 1, x - 1, y - 1) << endl;
  71. 	}
  72.  
  73. 	return 0;
  74. }
Runtime error #stdin #stdout 3.76s 0KB
comments (?)
stdin
copy 
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
stdout
copy 
Standard output is empty
https://ideone.com/0YPcYk
language:
C++14 (gcc 8.3)
created:
5 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!