fork download
copy 
  1. // just segt.. i want this one to TLE 
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct node{
  6. 	int count = 0;
  7. 	bool coin = false;
  8. 	};
  9. node st[500005];
  10. void init(int lo,int hi,int idx){
  11. 	for(int i=0;i<500005;i++){
  12. 		st[i].coin=false;
  13. 		st[i].count=0;
  14. 		}
  15. 	return;
  16. 	if(lo==hi){
  17. 		st[idx].coin=false;//means its tails...
  18. 		st[idx].count=0;
  19. 		return ;
  20. 		}
  21. 	init(lo,(lo+hi)/2,2*idx);
  22. 	init(((lo+hi)/2) +1,hi,2*idx+1);
  23. 	st[idx].count=(st[2*idx].count + st[2*idx+1].count);
  24. 	}
  25.  
  26. void flip(int lo,int hi,int s,int e,int idx){
  27. 	if(s>hi || e<lo)return ;
  28. 	if(lo==hi){
  29. 		st[lo].coin=1-st[lo].coin;
  30. 		if(st[lo].coin)st[lo].count=1;
  31. 		else st[lo].count=0;
  32. 		return ;
  33. 		}
  34. 	flip(lo,(lo+hi)/2, s,e,2*idx);
  35. 	flip(((lo+hi)/2) +1,hi, s,e,2*idx+1);
  36. 	st[idx].count=st[2*idx].count + st[2*idx+1].count;
  37. 	}
  38. node combine(node l,node r){
  39. 	node pp;
  40. 	pp.count=l.count+r.count;
  41. 	return pp;
  42. 	}
  43. node query(int lo,int hi,int s,int e,int idx){
  44. 	//if(s>hi || e<lo)return 0;//nasty..
  45. 	//if(lo>=s && hi<=e)return st[idx];
  46. 	if(s==lo && e==hi)
  47. 		return st[idx];
  48. 	int mid=((lo+hi)/2);
  49. 	if(mid>=e)
  50. 		return query(lo,mid,s,e,2*idx);
  51. 	else if(mid<s)
  52. 		return query(mid+1,hi,s,e,2*idx+1);
  53. 	return combine(query(lo,mid,s,mid,2*idx),query(mid+1,hi,mid+1,e,2*idx+1));
  54. 	}
  55. int main(){
  56. 	int n,q,i;
  57. 	//init(1,n,1);
  58. 	scanf("%d%d", &n,&q);
  59. 	for(i=0;i<q;i++){
  60. 		int tp,a,b;
  61. 		scanf("%d%d%d",&tp,&a,&b);
  62. 		//a+=1;b+=1;
  63. 		//if(tp==0)flip(1,n,a,b,1);
  64. 		printf("%d\n",(query(0,n-1,a,b,1)).count);
  65. 		}
  66. 	return 0;
  67. 	}
  68.  
Success #stdin #stdout 0s 7320KB
comments ()
stdin
copy 
4 7
1 0 3
0 1 2
1 0 1
1 0 0
0 0 3
1 0 3 
1 3 3
stdout
copy 
0
0
0
0
0
0
0
https://ideone.com/jPUedW
language:
C++ (gcc 8.3)
created:
9 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!