fork(1) download
copy 
  1. //============================================================================
  2. // Name        : SPOJ Multiple by 3 (Segment Tree)
  3. // Author      : Tarango Khan
  4. // Copyright   : Team Byteheads
  5. // Description : !!!Hello World!!!
  6. //============================================================================
  7.  
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10. #define Size 100005
  11.  
  12. struct vert{
  13.     int cnt[3];
  14.     int prop;
  15. };
  16. vert tree[Size*4];
  17.  
  18. void build_tree(int cur,int Start,int End){
  19.     if(Start == End){
  20.         tree[cur].cnt[0] = 1;
  21.         tree[cur].cnt[1] = 0;
  22.         tree[cur].cnt[2] = 0;
  23.         tree[cur].prop = 0;
  24.         return;
  25.     }
  26.     int left = cur*2;
  27.     int right = left+1;
  28.     int mid = (Start+End)/2;
  29.     build_tree(left,Start,mid);
  30.     build_tree(right,mid+1,End);
  31.     tree[cur].cnt[0] = tree[left].cnt[0] + tree[right].cnt[0];
  32.     tree[cur].cnt[1] = tree[left].cnt[1] + tree[right].cnt[1];
  33. 	tree[cur].cnt[2] = tree[left].cnt[2] + tree[right].cnt[2];
  34. 	tree[cur].prop = tree[left].prop + tree[right].prop;
  35. }
  36.  
  37. void update_prop(int cur){
  38. 	int tmp = tree[cur].cnt[2];
  39. 	tree[cur].cnt[2] = tree[cur].cnt[1];
  40. 	tree[cur].cnt[1] = tree[cur].cnt[0];
  41. 	tree[cur].cnt[0] = tmp;
  42. }
  43.  
  44. void update_child(int cur,int left,int right){
  45. 	tree[left].prop += tree[cur].prop;
  46. 	tree[right].prop += tree[cur].prop;
  47. 	int rotate  = tree[cur].prop%3;
  48. 	for(int s = 0;s<rotate;s++){
  49. 		update_prop(left);
  50. 		update_prop(right);
  51. 	}
  52. 	tree[cur].prop = 0;
  53. }
  54.  
  55. void update_tree(int cur,int Start,int End,int u,int v){
  56.     if(Start == u && End == v){
  57.     	tree[cur].prop += 1;
  58.     	update_prop(cur);
  59.         return;
  60.     }
  61.     int left = cur*2;
  62.     int right = left+1;
  63.     int mid = (Start+End)/2;
  64.  
  65.     if(tree[cur].prop != 0){ //If prop exist then we add that to his child and make his one to 0;
  66. 		update_child(cur,left,right);
  67. 	}
  68.  
  69.     if(v <= mid){
  70.     	update_tree(left,Start,mid,u,v);
  71.     }else if(u > mid){
  72.     	update_tree(right,mid+1,End,u,v);
  73.     }else{
  74.     	update_tree(left,Start,mid,u,mid);
  75.     	update_tree(right,mid+1,End,mid+1,v);
  76.     }
  77.     tree[cur].cnt[0] = tree[left].cnt[0] + tree[right].cnt[0];
  78.     tree[cur].cnt[1] = tree[left].cnt[1] + tree[right].cnt[1];
  79.     tree[cur].cnt[2] = tree[left].cnt[2] + tree[right].cnt[2];
  80. }
  81.  
  82. int tree_query(int cur,int Start,int End,int u,int v){
  83.     if(Start == u && End == v){
  84.     	return tree[cur].cnt[0];
  85.     }
  86.     int left = cur*2;
  87.     int right = left+1;
  88.     int mid = (Start+End)/2;
  89.     if(tree[cur].prop != 0){ //If prop exist then we add that to his child and make his one to 0;
  90.     	update_child(cur,left,right);
  91. 	}
  92.     if(v <= mid){
  93. 		return tree_query(left,Start,mid,u,v);
  94. 	}else if(u > mid){
  95. 		return tree_query(right,mid+1,End,u,v);
  96. 	}else{
  97. 		return tree_query(left,Start,mid,u,mid) + tree_query(right,mid+1,End,mid+1,v);
  98. 	}
  99. }
  100.  
  101. int main() {
  102.     int N,Q,u,v,type;
  103. 	scanf("%d %d",&N,&Q);
  104. 	build_tree(1,1,N);
  105. 	for(int i = 1;i<=Q;i++){
  106. 		scanf("%d",&type);
  107. 		if(type == 0){
  108. 			scanf("%d %d",&u,&v);
  109. 			u++;v++;
  110. 			update_tree(1,1,N,u,v);
  111. 		}else{
  112. 			scanf("%d %d",&u,&v);
  113. 			u++;v++;
  114. 			int sum = tree_query(1,1,N,u,v);
  115. 			printf("%d\n",sum);
  116. 		}
  117. 	}
  118.     return 0;
  119. }
  120.  
Success #stdin #stdout 0s 9392KB
comments (?)
stdin
copy 
4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3
stdout
copy 
4
1
0
2
https://ideone.com/IApyMo
language:
C++14 (gcc 8.3)
created:
8 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!