Ctrlalt в 00:51, 22 июля 2016

2016-07-22T00:51:03Z

← Предыдущая версия		Версия от 00:51, 22 июля 2016
Строка 107:		Строка 107:
	[[Category: Сборник задач: E-olymp]]		[[Category: Сборник задач: E-olymp]]
	[[Category: Задачи: Декартово дерево]]		[[Category: Задачи: Декартово дерево]]
	[[Category: Задачи: ~~set~~]]		[[Category: Задачи: Множество]]

Ctrlalt в 22:15, 24 апреля 2016

2016-04-24T22:15:32Z

← Предыдущая версия		Версия от 22:15, 24 апреля 2016
Строка 107:		Строка 107:
	[[Category: Сборник задач: E-olymp]]		[[Category: Сборник задач: E-olymp]]
	[[Category: Задачи: Декартово дерево]]		[[Category: Задачи: Декартово дерево]]
			[[Category: Задачи: set]]

Ctrlalt: Новая страница: «== Ссылки на задачу == * [http://www.e-olymp.com/ru/problems/686 E-olymp #686 — Следующий] * [http://informatics.mccme.ru/mod/stateme…»

2016-04-24T22:13:59Z

Новая страница: «== Ссылки на задачу == * [http://www.e-olymp.com/ru/problems/686 E-olymp #686 — Следующий] * [http://informatics.mccme.ru/mod/stateme…»

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

== Ссылки на задачу ==
* [http://www.e-olymp.com/ru/problems/686 E-olymp #686 — Следующий]
* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=2782 МЦНМО #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);
}
}
}

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

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

Ctrlalt в 00:51, 22 июля 2016

Ctrlalt в 22:15, 24 апреля 2016

Ctrlalt: Новая страница: «== Ссылки на задачу == * [http://www.e-olymp.com/ru/problems/686 E-olymp #686 — Следующий] * [http://informatics.mccme.ru/mod/stateme…»