fork download
copy 
  1. #include <cmath>
  2. #include <iostream>
  3. #define INF -15008
  4. using namespace std;
  5.  
  6. //	Function, that teturn lowest power of 2, bigger than a given number
  7. int lowestBiggerPowOf2Than(int number) {					
  8. 	int answer;
  9. 	answer = 1 << (int)(log2((double)number - 1) + 1);
  10. 	return answer;
  11. }
  12.  
  13. //	The structure describing the components from which consists a tree
  14. struct Node {
  15. 	int answer; 		
  16. 	int sumOnPrefix;
  17. 	int sumOnSuffix;
  18. 	int sumOnSegment;
  19. 	//	Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment
  20. 	Node() {
  21. 		answer = INF;
  22. 		sumOnPrefix = INF;
  23. 		sumOnSuffix = INF;
  24. 		sumOnSegment = INF;
  25. 	}
  26. 	// Constructs a node by a value of the initial sequence of numbers
  27. 	Node(int value) {
  28. 		answer = value;
  29. 		sumOnPrefix = value;
  30. 		sumOnSuffix = value;
  31. 		sumOnSegment = value;
  32. 	}
  33. };
  34.  
  35. //	Function, that merges two nodes (childs) and returns new node (parent)
  36. Node mergeNodes(Node leftChild, Node rightChild) {
  37. 	Node crossedNode;
  38. 	crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;
  39. 	crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);
  40. 	crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);
  41. 	crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));
  42. 	return crossedNode;
  43. }
  44.  
  45. //	Function, that building a tree recursive
  46. void build(int *base, Node *tree, int currentNode, int left, int right) {
  47. 	if (left == right) {
  48. 		tree[currentNode] = Node(base[left]);
  49. 	} else {
  50. 		int leftChild = 2 * currentNode;
  51. 		int middle = (left + right) / 2;
  52. 		build(base, tree, leftChild, left, middle);
  53. 		build(base, tree, leftChild + 1, middle + 1, right);
  54. 		// Use the previously described function to get the value of parent by his children
  55. 		tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);
  56. 	}
  57. }
  58.  
  59. // Funtion, that updates value in specified postion
  60. void update(Node *tree, int currentNode, int left, int right, int position, int newValue) { 
  61. 	if (left == right) {
  62. 		tree[currentNode] = Node(newValue);
  63. 	} else {
  64. 		int leftChild = 2 * currentNode;
  65. 		int middle = (left + right) / 2;
  66. 		if (position <= middle) {
  67. 			update(tree, leftChild, left, middle, position, newValue);
  68. 		} else {
  69. 			update(tree, leftChild + 1, middle + 1, right, position, newValue);
  70. 		}
  71. 		tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);
  72. 	}
  73. }
  74.  
  75. //	Function, that return node, storing the answer to the problem (subsegment with a maximum amount)
  76. Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
  77. 	if (left == leftBorder && right == rightBorder) {
  78. 		return tree[currentNode];
  79. 	}
  80. 	int leftChild = 2 * currentNode;
  81. 	int middle = (left + right) / 2;
  82. 	if (rightBorder <= middle) {
  83. 		return answer(tree, leftChild, left, middle, leftBorder, rightBorder);
  84. 	}
  85. 	if (leftBorder > middle) {
  86. 		return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
  87. 	}
  88. 	return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),
  89. 		answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));
  90. }
  91.  
  92. int main() {
  93. 	std::ios::sync_with_stdio(false);
  94. 	unsigned int quantityOfNumbers;
  95. 	cin >> quantityOfNumbers;
  96. 	int *base = new int[quantityOfNumbers];		//	A given sequence of numbers	
  97. 	for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {
  98. 		cin >> base[indexOfNumber];
  99. 	}
  100. 	int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
  101. 	Node *tree = new Node[sizeOfTree];
  102. 	build(base, tree, 1, 0, quantityOfNumbers - 1);
  103. 	unsigned int quantityOfRequests;
  104. 	cin >> quantityOfRequests;
  105. 	for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
  106. 		unsigned int request, leftBorder, rightBorder;
  107. 		cin >> request >> leftBorder >> rightBorder;
  108. 		if (request == 0) {
  109. 			update(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder);
  110. 		} else if (request == 1) {
  111. 			cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;
  112. 		}
  113. 	}
  114. 	return 0;
  115. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
stdout
copy 
6
4
-3
https://ideone.com/Vkkb8h
e-olymp 2906!!!!!
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!