E-olymp 5293

Ссылка на задачу

• E-olymp #5293 — Декартово дерево

Комментарии

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

Решение

#include <stdio.h>
#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();
}