Темы --> Информатика --> Структуры данных --> Деревья
    Куча(30 задач)
    Двоичное дерево поиска(24 задач)
    Дерево отрезков, RSQ, RMQ(90 задач)
    Бор(14 задач)
    Дерево Фенвика(6 задач)
    Декартово дерево(10 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> Жаутыковские олимпиады
    2011(8 задач)
Страница: 1 Отображать по:
#111878
Взвешивание камней
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Джек нашел \(N\) камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий  2 и так далее, самый тяжелый получил номер \(N\).

У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.

Ваша задача — определить состояние весов после добавления каждого камня. Точные массы камней не известны — даются только их номера.

Входные данные

Первая строка содержит целое число \(N\) (1 \(\le\) \(N\) \(\le\) 100000).

Каждая из следующих \(N\) строк содержит по два целых числа: \(R\) (1 \(\le\) \(R\) \(\le\) \(N\)) и \(S\) (1 \(\le\) \(S\) \(\le\) 2). \(R\)  номер камня, который будет положен на чашу \(S\). Все \(R\) будут различны.

Выходные данные

Выведите \(N\) строк  по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры
Входные данные
5
1 2
3 1
2 1
4 2
5 1
Выходные данные
<
>
>
?
>
#111881
Коллайдер
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Физики проводят эксперимент для исследования частиц трёх типов: \(x\), \(y\) и \(z\). Они запускают в коллайдер пронумерованный ряд из \(n\) частиц. Во время эксперимента происходит воздействие на одну конкретную частицу, после чего частица исчезает с \(i\)-ого места ряда и моментально появляется на месте \(j\). После её исчезновения номера частиц, стоящих правее, уменьшаются на 1, а после появления, номера частиц, стоящих правее, увеличиваются на 1. После определенного числа воздействий физики интересуются какая частица стоит на месте \(k\). Напишите программу, которая поможет физикам.

Входные данные

В первой строке файла два целых числа: \(n\) – количество частиц и m — общее количество воздействий и вопросов (1 \(\le\) \(n\) \(\le\) 1000000, 1 \(\le\) \(m\) \(\le\) 15000). Во второй строке — последовательность из символов \(x\), \(y\) и \(z\) длиной \(n\). На каждой из следующих \(m\) строк (1 \(\le\) \( m\) \(\le\) 15000) описано воздействие или вопрос. Строка, в которой описано воздействие, начинается символом \(a\) и после пробела дается два целых числа из интервала [1; \(n\)]. Первое из них показывает начальное, а второе  конечное местоположение частицы во время воздействия. Строка, в которой описан вопрос, начинается символом \(q\) и после пробела дается одно целое число из интервала [1; \(n\)]. Оно указывает позицию, которая интересует физиков.

Выходные данные

Выведите столько строк, сколько вопросов во входном файле. В строке номер \(i\) надо записать ответ на вопрос \(i\) — название соответствующей частицы \(x\), \(y\) или \(z\).

Пояснения к примеру

Последовательность после первого воздействия – xxyyzxxzxzyyzyx, последовательность после второго воздействия – xxyxyzxxzxzyyzy, последовательность после третьего воздействия – xyxyxyzxxzxzyzy,

Примеры
Входные данные
15 6
xzxyyzxxzxyyzyx
a 2 10
a 15 4
q 3
a 12 2
q 14
q 2
Выходные данные
y
z
y
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест