fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. struct Node
  6. {
  7. 	Node* lchild;
  8. 	Node* rchild;
  9. 	int val;
  10. };
  11.  
  12. void build(Node* node, int* base, int l, int r)
  13. {
  14. 	if (l == r)
  15. 		node->val = base[l-1];
  16. 	else
  17. 	{
  18. 		int m = (l + r) / 2;
  19. 		node->lchild = new Node();
  20. 		build(node->lchild, base, l, m);
  21. 		node->rchild = new  Node();
  22. 		build(node->rchild, base, m + 1, r);
  23. 	}
  24. }
  25.  
  26. void add(Node* to, Node* from, int l, int r, int npos, int nv)
  27. {
  28. 	if (l == r)
  29. 		to->val = nv;
  30. 	else
  31. 	{
  32. 		int m = (l + r) / 2;
  33. 		if (npos <= m)
  34. 		{
  35. 			to->rchild = from->rchild;
  36. 			Node* left = new Node();
  37. 			add(left, from->lchild, l, m, npos, nv);
  38. 			to->lchild = left;
  39. 		}
  40. 		else
  41. 		{
  42. 			to->lchild = from->lchild;
  43. 			Node* right = new Node();
  44. 			add(right, from->rchild, m + 1, r, npos, nv);
  45. 			to->rchild = right;
  46. 		}
  47. 	}
  48. }
  49.  
  50. int get(Node* node, int l, int r, int pos)
  51. {
  52. 	if (l == r)
  53. 		return node->val;
  54. 	else
  55. 	{
  56. 		int m = (l + r) / 2;
  57. 		if (pos <= m)
  58. 			return get(node->lchild, l, m, pos);
  59. 		else
  60. 			return get(node->rchild, m + 1, r, pos);
  61. 	}
  62. }
  63.  
  64. int main() 
  65. {
  66. 	ios::sync_with_stdio(false);
  67. 	int n;
  68. 	cin >> n;
  69. 	int base[n];
  70. 	for (int i = 0; i < n; i++)
  71. 		cin >> base[i];
  72. 	vector<Node*> versions;
  73. 	versions.push_back(new Node());
  74. 	build(versions.at(0), base, 1, n);
  75. 	int k;
  76. 	cin >> k;
  77. 	for (int i = 0; i < k; i++)
  78. 	{
  79. 		string s;
  80. 		cin >> s;
  81. 		if (s == "create")
  82. 		{
  83. 			int rootPos, newPos, newVal;
  84. 			cin >> rootPos >> newPos >> newVal;
  85. 			versions.push_back(new Node());
  86. 			add(versions.back(), versions.at(rootPos-1), 1, n, newPos, newVal);
  87. 		}
  88. 		else
  89. 		{
  90. 			int rootPos, valPos;
  91. 			cin >> rootPos >> valPos;
  92. 			cout << get(versions.at(rootPos-1), 1, n, valPos) << endl;
  93. 		}
  94. 	}
  95. 	return 0;
  96. }
Success #stdin #stdout 0s 3412KB
comments (?)
stdin
copy 
2
42 2048
17
create 1 1 1
create 2 2 1
create 3 2 5
create 3 1 4
create 5 2 6
get 1 1
get 1 2
get 2 1
get 2 2
get 3 1
get 3 2
get 4 1
get 4 2
get 5 1
get 5 2
get 6 1
get 6 2
stdout
copy 
42
2048
1
2048
1
1
1
5
4
1
4
6
https://ideone.com/UieN0X
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!