fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define endl "\n"
  5.  
  6. struct event
  7. {
  8. 	ll x, y1, y2, type;
  9. 	bool operator<(const event &other) const
  10. 	{
  11. 		return x < other.x || (x == other.x && type < other.type);
  12. 	}
  13. };
  14.  
  15. struct dynamicSegmentTree
  16. {
  17. #define mid (left + ((right - left) >> 1))
  18. private:
  19. 	struct Node
  20. 	{
  21. 		ll Value;
  22. 		ll count; // Number of positive values
  23. 		Node *LeftChild, *RightChild;
  24.  
  25. 		Node()
  26. 		{
  27. 			Value = 0;
  28. 			count = 0;
  29. 			LeftChild = nullptr;
  30. 			RightChild = nullptr;
  31. 		}
  32. 		Node(const ll &val)
  33. 		{
  34. 			Value = val;
  35. 			count = (val > 0) ? 1 : 0;
  36. 			LeftChild = nullptr;
  37. 			RightChild = nullptr;
  38. 		}
  39.  
  40. 		void createChildren(const ll val = 0)
  41. 		{
  42. 			if (LeftChild == nullptr)
  43. 				LeftChild = new Node(val);
  44. 			if (RightChild == nullptr)
  45. 				RightChild = new Node(val);
  46. 		}
  47. 		~Node()
  48. 		{
  49. 			delete LeftChild;
  50. 			delete RightChild;
  51. 			LeftChild = nullptr;
  52. 			RightChild = nullptr;
  53. 		}
  54. 	};
  55. 	ll N;
  56.  
  57. 	ll merge(const ll &leftNode, const ll &rightNode)
  58. 	{
  59. 		return leftNode + rightNode;
  60. 	}
  61.  
  62. 	ll mergeBinary(const Node *node)
  63. 	{
  64. 		ll leftCount = node->LeftChild ? node->LeftChild->count : 0;
  65. 		ll rightCount = node->RightChild ? node->RightChild->count : 0;
  66. 		return leftCount + rightCount;
  67. 	}
  68.  
  69. 	void push(ll left, ll right, Node *segNode, Node *lazyNode)
  70. 	{
  71. 		if (segNode == nullptr || lazyNode == nullptr || lazyNode->Value == 0)
  72. 			return;
  73.  
  74. 		segNode->Value += (right - left + 1) * lazyNode->Value;
  75. 		segNode->count = (segNode->Value > 0) ? (right - left + 1) : 0;
  76.  
  77. 		if (left != right)
  78. 		{
  79. 			segNode->createChildren();
  80. 			lazyNode->createChildren();
  81. 			lazyNode->LeftChild->Value += lazyNode->Value;
  82. 			lazyNode->RightChild->Value += lazyNode->Value;
  83. 		}
  84. 		lazyNode->Value = 0;
  85. 	}
  86.  
  87. 	void update(ll left, ll right, Node *segNode, Node *lazyNode, ll leftQuery, ll rightQuery, const ll &val)
  88. 	{
  89. 		push(left, right, segNode, lazyNode);
  90.  
  91. 		if (left > rightQuery || right < leftQuery)
  92. 			return;
  93.  
  94. 		if (left >= leftQuery && right <= rightQuery)
  95. 		{
  96. 			lazyNode->Value += val;
  97. 			push(left, right, segNode, lazyNode);
  98. 			return;
  99. 		}
  100.  
  101. 		segNode->createChildren();
  102. 		lazyNode->createChildren();
  103.  
  104. 		update(left, mid, segNode->LeftChild, lazyNode->LeftChild, leftQuery, rightQuery, val);
  105. 		update(mid + 1, right, segNode->RightChild, lazyNode->RightChild, leftQuery, rightQuery, val);
  106.  
  107. 		segNode->Value = merge(segNode->LeftChild->Value, segNode->RightChild->Value);
  108. 		segNode->count = mergeBinary(segNode);
  109. 	}
  110.  
  111. 	ll query(ll left, ll right, Node *segNode, Node *lazyNode, ll leftQuery, ll rightQuery)
  112. 	{
  113. 		if (left > rightQuery || right < leftQuery)
  114. 			return 0;
  115.  
  116. 		push(left, right, segNode, lazyNode);
  117.  
  118. 		if (leftQuery <= left && right <= rightQuery)
  119. 			return segNode->count;
  120.  
  121. 		segNode->createChildren();
  122. 		lazyNode->createChildren();
  123.  
  124. 		ll leftSegment = query(left, mid, segNode->LeftChild, lazyNode->LeftChild, leftQuery, rightQuery);
  125. 		ll rightSegment = query(mid + 1, right, segNode->RightChild, lazyNode->RightChild, leftQuery, rightQuery);
  126.  
  127. 		return leftSegment + rightSegment;
  128. 	}
  129.  
  130. public:
  131. 	Node *segRoot;
  132. 	Node *lazyRoot;
  133. 	dynamicSegmentTree()
  134. 	{
  135. 		segRoot = new Node();
  136. 		lazyRoot = new Node();
  137. 		N = (1LL << 50);
  138. 	}
  139. 	// Frees all dynamically allocated nodes
  140. 	void clear()
  141. 	{
  142. 		delete segRoot;
  143. 		delete lazyRoot;
  144. 		segRoot = new Node();
  145. 		lazyRoot = new Node();
  146. 	}
  147. 	void update(ll left, ll right, const ll &val)
  148. 	{
  149. 		update(1, N, segRoot, lazyRoot, left, right, val);
  150. 	}
  151.  
  152. 	ll query(ll M)
  153. 	{
  154. 		return query(1, N, segRoot, lazyRoot, 1, M);
  155. 	}
  156. #undef mid
  157. };
  158.  
  159. ll calculateUnionArea(vector<event> &events, int M)
  160. {
  161. 	sort(events.begin(), events.end());
  162. 	dynamicSegmentTree segTree;
  163.  
  164. 	ll prevX = 0, totalArea = 0, prevCoveredLength = 0;
  165. 	for (const auto &e : events)
  166. 	{
  167. 		ll curX = e.x;
  168. 		if (prevCoveredLength > 0)
  169. 			totalArea += prevCoveredLength * (curX - prevX); // Add covered area
  170.  
  171. 		segTree.update(e.y1, e.y2, e.type); // Update segment tree
  172. 		prevX = curX;
  173. 		prevCoveredLength = segTree.query(M);
  174. 	}
  175. 	segTree.clear();
  176. 	return totalArea;
  177. }
  178.  
  179. int main()
  180. {
  181. 	ios_base::sync_with_stdio(false);
  182. 	cin.tie(nullptr);
  183.  
  184. #ifndef ONLINE_JUDGE
  185. 	freopen("input.txt", "r", stdin);
  186. 	freopen("Output.txt", "w", stdout);
  187. #endif
  188. 	int t = 1;
  189. 	cin >> t;
  190. 	while (t--)
  191. 	{
  192. 		ll N, M, Q;
  193. 		cin >> N >> M >> Q;
  194. 		vector<event> events;
  195. 		while (Q--)
  196. 		{
  197. 			ll X, Y, S;
  198. 			cin >> X >> Y >> S;
  199.  
  200. 			ll X1 = max(X - S, 1LL);
  201. 			ll Y1 = max(Y - S, 1LL);
  202. 			ll X2 = min(X + S, N);
  203. 			ll Y2 = min(Y + S, M);
  204. 			events.push_back({X1, Y1, Y2, 1});
  205. 			events.push_back({X2 + 1, Y1, Y2, -1});
  206. 		}
  207.  
  208. 		cout << calculateUnionArea(events, M) << endl;
  209. 	}
  210. 	return 0;
  211. }
  212.  
  213.  
Success #stdin #stdout #stderr 0.27s 40872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "using namespace"
Execution halted
https://ideone.com/v7wUT5
language:
R (R 3.5.2)
created:
3 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!