E-olymp 686

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

• E-olymp #686 — Следующий
• МЦНМО #2782 — Следующий

Похожие задачи

• МЦНМО 2782

Решение

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

class Treap {

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

    int getKeysMin(TreapNode *node) {
        return node ? node->keysMin : 1 << 30;
    }

    void update(TreapNode *node) {
        if (!node)
            return;
        node->keysMin = min(node->key, min(getKeysMin(node->left), getKeysMin(node->right)));
    }

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

public:

    Treap() : root(0) {}

    void insertUnique(int key) {
        TreapNode *tLess, *tEqual, *tGreater;
        split(root, key, tLess, tGreater);
        split(tGreater, key + 1, tEqual, tGreater);
        if (!tEqual)
            tEqual = new TreapNode(key);
        root = merge(tLess, merge(tEqual, tGreater));
    }

    int next(int key) {
        TreapNode *tLess, *tNotLess;
        split(root, key, tLess, tNotLess);
        int result = getKeysMin(tNotLess);
        root = merge(tLess, tNotLess);
        return result != 1 << 30 ? result : -1;
    }

} treap;

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

    int queriesCount;
    scanf("%d", &queriesCount);
    int previousResult = 0;
    for (int i = 0; i < queriesCount; i++) {
        char queryType;
        int key;
        scanf(" %c%d", &queryType, &key);
        if (queryType == '+') {
            treap.insertUnique((key + previousResult) % (int)1e9);
            previousResult = 0;
        } else {
            previousResult = treap.next(key);
            printf("%d\n", previousResult);
        }
    }
}