fork(2) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. #define max(a, b) (a>b?a:b)
  5. int tree[100005], lazy[100005];
  6. void init(int idx, int l, int r){
  7. 	if(l>r)
  8. 		return ;
  9. 	if(l==r){
  10. 		tree[idx] = 0;
  11. 		lazy[idx] = -1;
  12. 	}
  13. 	else {
  14. 		tree[idx] = 0;
  15. 		lazy[idx] = -1;
  16. 		int mid = (l+r)/2;
  17. 		init(2*idx, l, mid);
  18. 		init(2*idx+1, mid+1, r);
  19. 	}
  20. }
  21. void update(int idx, int l, int r, int a, int b, int val, bool isReset){
  22. 	if(l>r || b<l || a>r){
  23. 		return;
  24. 	}
  25. 	// printf("idx=%d l=%d r=%d a=%d b=%d val=%d\n",idx,l,r,a,b,val);
  26. 	if(lazy[idx] != -1){
  27. 		tree[idx] = max(tree[idx], lazy[idx]);
  28. 		lazy[2*idx] = max(lazy[2*idx], lazy[idx]);
  29. 		lazy[2*idx+1] = max(lazy[2*idx+1], lazy[idx]);
  30. 		lazy[idx] = -1;
  31. 	}
  32. 	if(l>=a && r<=b){
  33. 		// printf("updating\n");
  34. 		tree[idx] = max(tree[idx], val);
  35. 		if(isReset){
  36. 			tree[idx] = val;
  37. 		}
  38. 		lazy[2*idx] = max(lazy[2*idx], val);
  39. 		lazy[2*idx+1] = max(lazy[2*idx+1], val);
  40. 		lazy[idx] = -1;
  41. 	}
  42. 	else {
  43. 		int mid = (l+r)/2;
  44. 		update(2*idx, l, mid, a, b, val, isReset);
  45. 		update(2*idx+1, mid+1, r, a, b, val, isReset);
  46. 		tree[idx] = max(tree[2*idx], tree[2*idx+1]);
  47. 	}
  48. }
  49. int query(int idx, int l, int r, int a){
  50. 	if(l>r || a<l || a>r){
  51. 		return -1;
  52. 	}
  53. 	// printf("idx=%d l=%d r=%d a=%d\n",idx,l,r,a);
  54. 	if(lazy[idx] != -1){
  55. 		tree[idx] = max(tree[idx], lazy[idx]);
  56. 		lazy[2*idx] = max(lazy[2*idx], lazy[idx]);
  57. 		lazy[2*idx+1] = max(lazy[2*idx+1], lazy[idx]);
  58. 		lazy[idx] = -1;
  59. 	}
  60. 	if(l==a && r==a){
  61. 		// printf("----l=%d r=%d a=%d tree=%d\n",l,r,a,tree[idx]);
  62. 		return tree[idx];
  63. 	}
  64. 	else {
  65. 		int mid = (l+r)/2;
  66. 		int left = query(2*idx, l, mid, a);
  67. 		int right = query(2*idx+1, mid+1, r, a);
  68. 		return max(left, right);
  69. 	}
  70. }
  71. int main() {
  72. 	init(1, 1, 10);
  73. 	update(1, 1, 10, 1, 4, 7, false);
  74. 	cout << query(1, 1, 10, 3) << endl;
  75. 	update(1, 1, 10, 3, 3, 9, false);
  76. 	cout << query(1, 1, 10, 3) << endl;
  77. 	update(1, 1, 10, 3, 3, 0, true);
  78. 	cout << query(1, 1, 10, 3) << endl;
  79. 	return 0;
  80. }
Success #stdin #stdout 0s 16848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7
9
0
https://ideone.com/Mkp4dQ
language:
C++ (gcc 8.3)
created:
6 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!