fork download
copy 
  1. #include <cmath>
  2. #include <ctime>
  3. #include <iostream>
  4. #define WHITE -1
  5. using namespace std;
  6.  
  7. const unsigned int TIME_CONVERSION_CONSTANT = 1000;
  8.  
  9. //  Function, that teturn lowest power of 2, bigger than a given number
  10. int lowestBiggerPowOf2Than(int number) {					
  11. 	int answer;
  12. 	answer = 1 << (int)(log2((double)number - 1) + 1);
  13. 	return answer;
  14. }
  15.  
  16. //  The structure describing the components from which consists a tree
  17. struct Node {
  18. 	int color;
  19. 	long long sumOnSegment;
  20. 	// The default constructor
  21. 	Node() {
  22. 		color = WHITE;
  23. 		sumOnSegment = 0;
  24. 	}
  25. 	//	Construct the node by its color and sum on corresponding segment
  26. 	Node(int color, long long sumOnSegment) {
  27. 		this->color = color;
  28. 		this->sumOnSegment = sumOnSegment;
  29. 	}
  30. 	//	Define, if this node is painted in some color (some number is assigned)
  31. 	bool isColored() {
  32. 		return color != WHITE;
  33. 	}
  34. };
  35.  
  36. //	Function, that pushes information from parent to the children
  37. void push(Node *tree, int currentNode, int left, int right) {
  38. 	if (tree[currentNode].isColored()) {
  39. 		int middle = (left + right) / 2;
  40. 		int leftChild = 2 * currentNode;
  41. 		tree[leftChild].color = tree[currentNode].color;
  42. 		tree[leftChild + 1].color = tree[currentNode].color;
  43. 		tree[leftChild].sumOnSegment = (long long)(middle - left + 1) * tree[leftChild].color;
  44. 		tree[leftChild + 1].sumOnSegment = (long long)(right - middle) * tree[leftChild + 1].color;
  45. 		tree[currentNode].color = WHITE;
  46. 	}
  47. }
  48.  
  49. //	Function, that updates the value of all nodes on a segment for the specified 
  50. void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color) {
  51. 	if (leftBorder == left && rightBorder == right) {
  52. 		tree[currentNode] = Node(color, (long long)(right - left + 1) * color);
  53. 	} else {
  54. 		push(tree, currentNode, left, right);
  55. 		int leftChild = 2 * currentNode;
  56. 		int middle = (left + right) / 2;
  57. 		if (rightBorder <= middle) {
  58. 			update(tree, leftChild, left, middle, leftBorder, rightBorder, color);
  59. 		} else if (leftBorder >= middle + 1) {
  60. 			update(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder, color);
  61. 		} else {
  62. 			update(tree, leftChild, left, middle, leftBorder, middle, color);
  63. 			update(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder, color);
  64. 		}
  65. 		tree[currentNode].sumOnSegment = tree[leftChild].sumOnSegment + tree[leftChild + 1].sumOnSegment;
  66. 	} 
  67. }
  68.  
  69. // Function, that returns an array element by its position
  70. Node getElement(Node *tree, int currentNode, int left, int right, int position) {
  71. 	if (left == right) {
  72. 		return tree[currentNode];
  73. 	} else {
  74. 		// Executes the retarded delayed update (pushes information)
  75. 		push(tree, currentNode, left, right);
  76. 		int middle = (left + right) / 2;
  77. 		int leftChild = currentNode * 2;
  78. 		if (position <= middle) {
  79. 			return getElement(tree, leftChild, left, middle, position);
  80. 		} else {
  81. 			return getElement(tree, leftChild + 1, middle + 1, right, position);
  82. 		}
  83. 	}
  84. }
  85.  
  86. //	Function, that calculates the sum at a specified segment
  87. long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
  88. 	if (left == leftBorder && right == rightBorder) {
  89. 		return tree[currentNode].sumOnSegment;
  90. 	} else {
  91. 		// Executes the retarded delayed update (pushes information)
  92. 		push(tree, currentNode, left, right);
  93. 		int leftChild = 2 * currentNode;
  94. 		int middle = (left + right) / 2;
  95. 		if (rightBorder <= middle) {
  96. 			return sum(tree, leftChild, left, middle, leftBorder, rightBorder);
  97. 		} else if (leftBorder >= middle + 1) {
  98. 			return sum(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
  99. 		} else {
  100. 			return sum(tree, leftChild, left, middle, leftBorder, middle) 
  101. 				+ sum(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder);
  102. 		}
  103. 	}
  104. }
  105.  
  106. int main() {
  107. 	clock_t startTime;
  108. 	ios::sync_with_stdio(false);
  109. 	unsigned int quantityOfNumbers;
  110. 	cin >> quantityOfNumbers;
  111. 	unsigned int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
  112. 	Node *tree = new Node[sizeOfTree];
  113. 	unsigned int quantityOfRequests;
  114. 	cin >> quantityOfRequests;
  115. 	for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
  116. 		char request;
  117. 		cin >> request;
  118. 		unsigned int leftBorder, rightBorder;
  119. 		if (request == 'A') {
  120. 			int value;
  121. 			cin >> leftBorder >> rightBorder >> value;
  122. 			update(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1, value);
  123. 		} else if (request == 'Q') {
  124. 			cin >> leftBorder >> rightBorder;
  125. 			cout << sum(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1) << endl;
  126. 		}
  127. 	}
  128. 	cout << "Working time: " << (clock() - startTime) / (double) (CLOCKS_PER_SEC / TIME_CONVERSION_CONSTANT) << " ms" << endl;
  129. 	return 0;
  130. }
Success #stdin #stdout 0s 6532KB
comments (?)
stdin
copy 
100000 4
A 1 100000 1000000000
Q 1 100000
A 1 100000 0
Q 1 100000
stdout
copy 
100000000000000
0
Working time: 8.509 ms
https://ideone.com/h3Qd3M
e-olymp 2307!!!!
language:
C++14 (gcc 8.3)
created:
8 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!