Темы --> Информатика --> Структуры данных --> Деревья --> Декартово дерево
---> 3 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 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
#113251
Подчисло
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Петрик и Василько — настоящие друзья, поэтому они постоянно задают друг другу всевозможные интересные задачи. Однако Василько всегда с легкостью решает задачи своего друга, поэтому Петрик решил придумать по-настоящему сложную задачу. И вот что у него получилось. Будем называть число b подчислом числа a , если из числа a можно вычеркнуть некоторые цифры так, что цифры, которые остались, образуют число b . Задано n -цифровое число x . Обозначим как x k наибольшее k -цифровое подчисло числа x . Необходимо ответить на m запросов. Каждый запрос состоит из двух цифр - k и l . Ответом на запрос является l -я цифра числа x k . На этот раз задача действительно заставила Василько задуматься. А сможете ли вы решить ее быстрее его?

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

В первой строке входного файла содержится целое число x длины n ( 1 ≤ n ≤ 100 000 ). Во второй строке содержится число m ( 1 ≤ m ≤ 50 000 ). В следующих m строках содержится по два числа k i , l i ( 1 ≤ k i ≤ n , 1 ≤ l i ≤ k i ) — параметры i -го запроса.

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

Выходной файл должен содержать одну строку длины m , i -й символ которого является ответом на i -й запрос.

Примечание

  1. n = 20, m = 10 000 .( 15 баллов)
  2. n · m ≤ 500 000 .( 25 баллов)
  3. n ≤ 100 000, m ≤ 50 000 .( 60 баллов)
Примеры
Входные данные
31415926
7
2 2
3 1
1 1
4 3
5 2
8 2
7 3
Выходные данные
6992511
#113581
Массивы, числа, три хеша
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Массивы, числа, три хеша ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Вам дан массив целых чисел длины N . Пусть s 1 , s 2 , ... , s q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.

Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 N - 1 .

Массив A лексикографически меньше массива B , если A i < B i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .

Определим хеш массива s , состоящего из элементов v 1 , v 2 , ... , v p , как: h ( s )  =  ( v 1 · B p - 1 + v 2 · B p - 2 + ... + v p - 1 · B + v p ) mod M , где B и M - данные числа.

Посчитайте h ( s 1 ) , h ( s 2 ) , ... , h ( s K ) для данного K .

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

В первой строке содержатся числа N , K , B , M ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 100000 , 1 ≤ B , M ≤ 1000000 ).

Во второй строке содержится N чисел a 1 , a 2 , a 3 , ... , a N ( 1 ≤ a i ≤ 100000 ).

Гарантируется, что во всех тестах K ≤ 2 N - 1 .

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

Выведите K строк, j -я строка должна содержать h ( s j ) и длину s j .

Примечание

Решения, работающие при 1 ≤ a 1 , a 2 , ..., a N ≤ 30 , будут оцениваться в 60 баллов.

Примеры
Входные данные
2 3 1 5
1 2
Выходные данные
1 1
3 2
2 1
Входные данные
3 4 2 3
1 3 1
Выходные данные
1 1
1 1
0 2
2 2
Входные данные
5 6 23 1000
1 2 4 2 3
Выходные данные
1 1
25 2
25 2
577 3
274 4
578 3
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест