Ctrlalt: /* Решение */

2016-04-24T21:41:24Z

Решение

← Предыдущая версия		Версия от 21:41, 24 апреля 2016
Строка 7:		Строка 7:
	== Решение ==		== Решение ==
	#include <stdio.h>		#include <stdio.h>
	~~#include <tuple>~~
	#include <vector>		#include <vector>
	#include <algorithm>		#include <algorithm>

Ctrlalt: Новая страница: «== Ссылка на задачу == * [http://www.e-olymp.com/ru/problems/5293 E-olymp #5293 — Декартово дерево] == Комментарии …»

2016-04-24T21:10:01Z

Новая страница: «== Ссылка на задачу == * [http://www.e-olymp.com/ru/problems/5293 E-olymp #5293 — Декартово дерево] == Комментарии …»

Новая страница

== Ссылка на задачу ==
* [http://www.e-olymp.com/ru/problems/5293 E-olymp #5293 — Декартово дерево]

== Комментарии ==
По приоритетам узлы декартова дерева должны образовывать минимальную, а не максимальную кучу.

== Решение ==
#include <stdio.h>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;

struct KeyValuePriorityNode {
int key, value, priority;
KeyValuePriorityNode(int key, int value, int priority) : key(key), value(value), priority(priority) {}
bool operator < (const KeyValuePriorityNode &that) const {
return key < that.key;
}
};

class Treap {

struct TreapNode {
int key, value, priority;
TreapNode *left, *right;
TreapNode(int key, int value, int priority) : key(key), value(value), priority(priority), left(0), right(0) {}
TreapNode(int key, int value, int priority, TreapNode *left, TreapNode *right) : key(key), value(value), priority(priority), left(left), right(right) {}
} *root;

TreapNode *merge(TreapNode *a, TreapNode *b) {
if (!a || !b)
return a ? a : b;
if (a->priority > b->priority) {
a->right = merge(a->right, b);
return a;
} else {
b->left = merge(a, b->left);
return b;
}
}

void split(TreapNode *t, int splitKey, TreapNode *&a, TreapNode *&b) {
if (!t) {
a = b = 0;
return;
}
if (t->key < splitKey) {
split(t->right, splitKey, t->right, b);
a = t;
} else {
split(t->left, splitKey, a, t->left);
b = t;
}
}

void recursivePrintNodeValues(TreapNode *currentNode, int parentValue) {
if (!currentNode)
return;
int leftValue = currentNode->left ? currentNode->left->value : 0;
int rightValue = currentNode->right ? currentNode->right->value : 0;
printf("%d %d %d\n", parentValue, leftValue, rightValue);
recursivePrintNodeValues(currentNode->left, currentNode->value);
recursivePrintNodeValues(currentNode->right, currentNode->value);
}

public:

Treap() : root(0) {}

Treap(vector<KeyValuePriorityNode> nodes) {
root = 0;
sort(nodes.begin(), nodes.end());
vector<TreapNode *> rightNodes;
for (int i = 0; i < nodes.size(); i++) {
while (!rightNodes.empty() && rightNodes.back()->priority < nodes[i].priority)
rightNodes.pop_back();
TreapNode *&pointerToNewNode = rightNodes.empty() ? root : rightNodes.back()->right;
TreapNode *newNode = new TreapNode(nodes[i].key, nodes[i].value, nodes[i].priority, pointerToNewNode, 0);
pointerToNewNode = newNode;
rightNodes.push_back(newNode);
}

}

void printNodeValues() {
recursivePrintNodeValues(root, 0);
}

};

int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

int pairsCount;
scanf("%d", &pairsCount);
vector<KeyValuePriorityNode> nodes;
for (int i = 0; i < pairsCount; i++) {
int key, priority;
scanf("%d%d", &key, &priority);
nodes.push_back(KeyValuePriorityNode(key, i + 1, -priority));
}
Treap treap(nodes);
printf("YES\n");
treap.printNodeValues();
}

[[Category: Сборник задач: E-olymp]]
[[Category: Задачи: Декартово дерево]]

E-olymp 5293 - История изменений

Ctrlalt: /* Решение */

Ctrlalt: Новая страница: «== Ссылка на задачу == * [http://www.e-olymp.com/ru/problems/5293 E-olymp #5293 — Декартово дерево] == Комментарии …»