images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 22:03:07

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2395. Проверка заклинания

Ограничения: время – 300ms/600ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Сломанная волшебная палочка не слушалась Рона на уроке заклинаний и ударила в лоб профессору Флитвику. Теперь за свою неуклюжесть Рон должен сравнить части некоторого сложного заклинания на эквивалентность. Две последовательности букв `X` и `Y` являются эквивалентными, если буквы в `X` можно переставить таким образом, чтобы получилась последовательность `Y`.
Напишите программу, которая сравнивает эквивалентность подстрок некоторого заклинания.
Первая строка входного файла содержит одну строку `S`. Вторая строка содержит одно целое число `n` – количество запросов. Последующие `n` строк содержат по четыре целых числа `i_1,\ j_1,\ i_2,\ j_2` (`1\ ≤\ i_1\ ≤\ j_1\ ≤\ |S|`, `1\ ≤\ i_2\ ≤\ j_2\ ≤\ |S|`) – запрос на проверку эквивалентности.
Для каждого запроса вывести на отдельной строке сообщение "YES", подстрока с `i_1`-го по `j_1`-й символ заклинания `S` эквивалентна подстроке с `i_2`-го по `j_2`-й символ этого заклинания, иначе вывести сообщение "NO".

Пример ввода 1

avadakedavra
2
2 4 8 10
1 1 2 2

Пример вывода 1

YES
NO

Пример ввода 2

apparate
2
1 3 3 4
1 3 3 5

Пример вывода 2

NO
NO
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача 1 (50 баллов)
`1\ ≤\ |S|\ ≤\ 1000`, `1 ≤ n ≤ 1000`
Подзадача 2 (50 баллов)
`1\ ≤\ |S|\ ≤\ 50\ 000`, `1 ≤ n ≤ 50\ 000`
Необходимые подзадачи: 1.
loading