fork download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. const int MAXN = 100000;
  5. struct node{
  6. 	int tail,flips,l,r;
  7. 	node *LEFT,*RIGHT;
  8. 	node(){
  9. 		l = r = tail = flips = 0;
  10. 		LEFT = NULL;
  11. 		RIGHT = NULL;
  12. 	}
  13. 	node(int x,int y,int t=0)
  14. 	{
  15. 		l = x;
  16. 		r = y;
  17. 		flips = 0;
  18. 		tail = t;
  19. 		LEFT = RIGHT = NULL;
  20. 	}
  21.  
  22. 	void merge()
  23. 	{
  24. 		tail = LEFT->tail + RIGHT->tail;
  25. 	}
  26.  
  27. 	node* build(int L,int R)
  28. 	{
  29. 		if(L == R)
  30. 		{
  31. 			return new node(L,R,1);
  32. 		}
  33. 		int mid = (L + R)>>1;
  34.  
  35. 		if(LEFT == NULL)
  36. 		{
  37. 			LEFT = new node(L,mid);
  38. 			LEFT = LEFT->build(L,mid);
  39. 		}
  40. 		if(RIGHT == NULL)
  41. 		{
  42. 			RIGHT = new node(mid+1,R);
  43. 			RIGHT = RIGHT->build(mid+1,R);
  44. 		}
  45. 		merge();
  46. 		return this;
  47. 	}
  48. 	void push()
  49. 	{
  50. 		if(LEFT != NULL)
  51. 			LEFT->flips += flips;
  52. 		if(RIGHT != NULL)
  53. 			RIGHT->flips += flips;
  54.  
  55. 		if(flips != 0 && flips%2 != 0)
  56. 		{
  57. 			tail = r - l + 1 - tail;
  58. 		}
  59. 		flips = 0;
  60. 		return;
  61. 	}
  62. 	void update(int x,int y)
  63. 	{
  64. 		push();
  65. 		if(x > r || y < l)
  66. 			return;
  67. 		if(x <= l && r <= y)
  68. 		{
  69. 			tail = r - l + 1 - tail;
  70. 			if(LEFT != NULL)
  71. 				LEFT->flips += 1;
  72. 			if(RIGHT != NULL)
  73. 				RIGHT->flips += 1;
  74. 			return;
  75. 		}
  76. 		LEFT->update(x,y);
  77. 		RIGHT->update(x,y);
  78. 		tail = RIGHT->tail + LEFT->tail;
  79. 	}
  80. 	int query(int x,int y)
  81. 	{
  82. 		push();
  83. 		if(r < x  || l > y)
  84. 			return 0;
  85. 		if(x <= l && r <= y)
  86. 		{
  87. 			return r - l + 1 - tail;
  88. 		}
  89. 		return LEFT->query(x,y) + RIGHT->query(x,y);
  90. 	}
  91. };
  92.  
  93. int main()
  94. {
  95. 	int n,m;
  96. 	cin >> n ;
  97. 	struct node root(0,n-1);
  98. 	root.build(0,n-1);
  99. 	cin >> m;
  100. 	//cout << 1<< '\n';
  101. 	for(int i = 0; i < m;++i)
  102. 	{
  103. 		int t,x,y;
  104. 		cin >> t >> x >> y;
  105. 		if(t == 0)
  106. 			root.update(x,y);
  107. 		else
  108. 			cout << root.query(x,y) << '\n';
  109. 	}
  110. }
  111.  
Runtime error #stdin #stdout #stderr 1.46s 1530880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'St9bad_alloc'
  what():  std::bad_alloc
https://ideone.com/YEy9sm
language:
C++14 (gcc 8.3)
created:
7 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!