Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2757. Декартово дерево
Учебные задачи: АиСД. Деревья. Множества, отображения, хеш-таблицы| 01/09/2007 | Алгоритмы и структуры данных. Деревья (A) |
Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
```c++
#include <iostream>
#include <utility>
#include <cstdlib>
using namespace std;
template <typename Key>
class Treap {
struct node {
Key x; int y;
node *left=nullptr, *right=nullptr;
node(Key x, int y) : x(x), y(y) { }
};
node *root=nullptr;
int n=0;
pair<node*, node*> split(node* t, Key k, bool eq) {
if (!t) return {nullptr,nullptr};
if (k > t->x || eq && k == t->x) {
auto [t1,t2]=split(t->right,k,eq);
t->right=t1;
return {t,t2};
} else {
auto [t1,t2]=split(t->left,k,eq);
t->left=t2;
return {t1,t};
}
}
node* merge(node* t1, node* t2) {
if(!t2) return t1;
if(!t1) return t2;
if (t1->y > t2->y) {
t1->right=merge(t1->right,t2);
return t1;
} else {
t2->left=merge(t1,t2->left);
return t2;
}
}
void free(node *t) {
if(!t) return;
free(t->left);
free(t->right);
delete t;
}
public:
Treap(){}
~Treap() { free(root); }
int size() const { return n; }
bool contains(Key k) {
node *p=root;
while(p) {
if(p->x==k) return 1;
else if(p->x>k) p=p->left;
else p=p->right;
}
return 0;
}
void insert(Key k) {
node *m=new node(k,rand());
auto [t1,t2]=split(root,k,0);
root=merge(merge(t1,m),t2);
++n;
}
void erase(Key k) {
auto [t1,t]=split(root, k, 0);
auto [m,t2]=split(t, k, 1);
root=merge(t1,t2);
if(m) --n;
free(m);
}
};
int main()
{ Treap<int> t;
t.insert(1);
t.insert(7);
t.insert(5);
cout<<t.contains(5)<<"\n";
cout<<t.contains(0)<<"\n";
t.erase(5);
cout<<t.contains(5)<<"\n";
cout<<t.contains(7)<<"\n";
}
```
Добавить поле для значения, связанного с ключом, (``Treap<int,int> t``), операцию доступа к значению по ключу (``t[k]``), добавления (``t.insert(k, v)``) и решить следующую задачу:
>8:05\
>Позвонил юзер, сказал, что забыл пароль. Посоветовал ему воспользоваться утилитой восстановления паролей, которая называется FDISK. Находясь в блаженном неведении, он меня поблагодарил и отключился. Господи, мы ведь еще позволяем таким людям водить машину и голосовать на выборах!
>
>8:14\
>Позвонил юзер с 8:05, сказал, что получил сообщение "Error accessing Drive 0." Сказал ему, что это ошибка операционной системы. Направил его в службу поддержки Майкрософт.
>
>15:00\
>Еще один юзер (похоже, новичок). Говорит, не работает макрос периодического запуска. Предложил добавить в конец кода макроса ``@DeleteDocument``. Пообещал прислать приложение к инструкции, где описан такой способ.
В ИТ-отделе ООО "Системные администраторы" есть колл-центр для ответов на вопросы пользователей. Цены на поддержку следующие:
1. Ответ на вопрос -- 10$
2. Правильный ответ на вопрос -- 20$
3. Правильный ответ на вопрос с объяснением -- 40$
4. Правильный ответ на вопрос, на который уже был дан правильный ответ -- +10$ за каждый предыдущий правильный ответ
Так, например, если пользователь трижды задает один и тот же вопрос, сначала получает неправильный ответ, затем правильный, а
в третий раз правильный ответ с объяснением, это будет стоить ему `10 + 20 + (40 + 1 * 10) = 80` $.
Счета пользователям выставляются ежемесячно в соответствии с журналом вызовов. Специалисты компании просматривают
журнал и по каждому вопросу определяют: уникальный номер, поэтому эквивалентные вопросы имеют одинаковые номера, был ли ответ
правильным, был ли ответ кратким или содержал достаточно подробное объяснение. Учитывая эти данные, ваша программа должна рассчитать сумму платежа.
Входной файл содержит количество вызовов `N` (`0<N<=100000`) от одного пользователя, затем следуют `N` троек `q_i a_i x_i`, где `q_i` — номер вопроса от 1 до `10^9`,
`a_i` = 1, если ответ был правильным, 0 в противном случае, `x_i = 1`, если было дано объяснение, 0 в противном случае.
Выходной файл должен содержать одно число -- сумма платежа для этого пользователя.
```sample Пример ввода 1
1
9834 0 1
```
```sample Пример вывода 1
10
```
```sample Пример ввода 2
3
33 1 0
33 0 0
33 1 1
```
```sample Пример ввода 2
80
```
