fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,m,q;
  4. struct Query
  5. {
  6. 	int x1,y1,x2,y2;
  7. };
  8. vector<vector<int>> inp;
  9. vector<Query> query;
  10. vector<int> seg;
  11. vector<int> lazy;
  12. vector<vector<int>> bit;
  13. void sub1()
  14. {
  15. 	int ans = 0;
  16. 	for(int i =1; i<=q; i++)
  17. 	{
  18. 		for(int a = query[i].x1; a<=query[i].x2; a++)
  19. 		{
  20. 			for(int b = query[i].y1; b<=query[i].y2; b++) 
  21. 			{
  22. 				if(inp[a][b])
  23. 				{
  24. 					ans--;
  25. 					inp[a][b] = 0;
  26. 				}
  27. 				else
  28. 				{
  29. 					ans++;
  30. 					inp[a][b] = 1;
  31. 				}
  32. 			}
  33. 		}
  34. 	}
  35. 	cout << ans;
  36. 	return;
  37. }
  38. void push(int id,int l, int r)
  39. {
  40. 	if(lazy[id] == 0 || l == r)return;
  41. 	int mid = (l+r)/2;
  42. 	lazy[id*2] +=lazy[id];
  43. 	lazy[id*2+1] += lazy[id];
  44. 	seg[id*2] += (mid - l + 1) * lazy[id];
  45. 	seg[id*2+1] += (r - mid) * lazy[id];
  46. 	lazy[id] = 0;
  47. 	return;
  48. }
  49. void update(int id, int l, int r, int u, int v)
  50. {
  51. 	if(u > r|| v< l ) return;
  52. 	if(u <= l && v >= r) 
  53. 	{
  54. 		seg[id] += (r-l+1);
  55. 		lazy[id]++;
  56. 		return;
  57. 	}
  58. 	push(id, l, r);
  59. 	int mid = (l+r)/2;
  60. 	update(id*2, l, mid, u, v);
  61. 	update(id*2+1, mid+1, r, u, v);
  62. 	seg[id]  = seg[id*2] + seg[id*2+1];
  63. }
  64.  
  65. int get(int id, int l, int r, int pos)
  66. {
  67. 	if(l == r) return seg[id];
  68. 	int mid = (l+r)/2;
  69. 	push(id, l, r);
  70. 	if(mid >= pos) return get(id*2, l, mid, pos);
  71. 	else return get(id*2+1, mid+1, r, pos);
  72. }
  73. void sub2()
  74. {
  75. 	seg.resize(4*m+1);
  76. 	lazy.resize(4*m+1);
  77. 	for(int  i =1; i<=q; i++)
  78. 	{
  79. 		int  l = query[i].y1, r = query[i].y2;
  80. 		update(1, 1, m, l, r);
  81. 	}
  82. 	int ans = 0;
  83. 	for(int i =1; i<=m; i++) {
  84. 		int tmp = get(1, 1, m, i);
  85. 		if(tmp % 2 != 0) ans++;
  86. 	}
  87. 	cout << ans;
  88. }
  89.  
  90. void addBIT(int x, int y,int val)
  91. {
  92. 	for(int  i = x; i<=n; i += i & -i)
  93. 		for(int  j = y; j<=m; j+= j  & -j) bit[i][j]+=val;
  94. }
  95.  
  96. void updateBIT(int x1, int y1, int x2, int y2)
  97. {
  98. 	addBIT(x1, y1, 1);
  99. 	addBIT(x2+1, y1, -1);
  100. 	addBIT(x1, y2+1, -1);
  101. 	addBIT(x2+1, y2+1, 1);
  102. 	return;
  103. }
  104.  
  105. int getBIT(int x, int y)
  106. {
  107. 	int res = 0;
  108. 	for(int  i = x; i>=1; i-= i &-i) for(int j = y; j >=1; j -= j& -j)res += bit[i][j];
  109. 	return res;
  110. }
  111.  
  112.  
  113. void sub3()
  114. {
  115. 	bit.resize(n+3, vector<int>(m+3));
  116. 	for(int  i =1; i<=q; i++)
  117. 	{
  118. 		updateBIT(query[i].x1, query[i].y1, query[i].x2, query[i].y2);
  119. 	}
  120. 	int ans = 0;
  121. 	for(int i =1; i<=n; i++)
  122. 	{
  123. 		for(int j =1; j<=m; j++)
  124. 		{
  125. 			int tmp =getBIT(i, j);
  126. 			if(tmp % 2 != 0) ans++;
  127. 		}
  128. 	}
  129. 	cout << ans;
  130. 	return;
  131. }
  132.  
  133.  
  134. int main()
  135. {
  136. 	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  137. 	cin >> n >> m >> q;
  138. 	inp.resize(n+1, vector<int>(m+1));
  139. 	query.resize(q+1);
  140. 	for(int i =1; i<=q; i++) 
  141. 	{
  142. 		int a,b,c,d; cin >> a >> b >> c >> d;
  143. 		query[i] = {a, b, c, d};
  144. 	}
  145. 	//sub1();
  146. 	//sub2();
  147. 	sub3();
  148.  
  149. 	return 0;
  150. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
1 3 2
1 1 1 2 
1 2 1 3
stdout
copy 
2
https://ideone.com/UPEk68
language:
C++14 (gcc 8.3)
created:
7 days 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!