Codeforces Beta Round 99 (Div. 1) |
---|
Закончено |
Катя совсем недавно начала придумывать задачи по программированию и делать свои контесты. Что ей не нравится — так это скучные и простые ограничения. «N не больше тысячи» и «сумма ai не больше миллиона» наскучили Кате, и она решила придумать что-нибудь посложнее.
В последней задаче на строки, придуманной Катей, входные данные — одна строка из маленьких латинских букв. Чтобы сделать условие подлиннее и вселить ужас в людей, решающих контест, Катя придумала следующий набор из k однотипных ограничений (символы в ограничениях могут повторяться, а некоторые ограничения могут и противоречить друг другу):
Однако, решив, что и это слишком просто и наглядно, Катя дописала следующее условие: из вышеуказанного списка строка удовлетворяет не менее, чем L, и не более, чем R ограничениям.
Составлять сложные и подлые тесты Катя не любит, поэтому она просто взяла большую строку s и хочет добавить в тесты все ее подстроки, которые удовлетворяют ограничениям. Однако, запутавшись в собственных условиях, Катя попросила Вас посчитать, сколько подстрок строки s удовлетворяет этим условиям (каждое вхождение подстроки считается отдельно).
В первой строке записана непустая строка s, состоящая из маленьких латинских букв. Длина строки s не превышает 105.
Во второй строке записаны три целых числа, разделенных пробелами — k, L и R (0 ≤ L ≤ R ≤ k ≤ 500).
В следующих k строках в формате «ci li ri» записаны ограничения, придуманные Катей. Все буквы ci — маленькие латинские буквы, li и ri — целые числа (0 ≤ li ≤ ri ≤ |s|, где |s| — длина строки s). Буквы ci не обязательно различны.
Выведите одно число — количество подстрок, удовлетворяющих ограничениям.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать поток cout или спецификатор %I64d.
codeforces
2 0 0
o 1 2
e 1 2
7
codeforces
2 1 1
o 1 2
o 1 2
0
В первом тесте требуется посчитать количество строк, не содержащих символов «e» и «o». Вот все такие строки (в порядке вхождения в исходную строку слева направо): «c», «d», «f», «r», «rc», «c», «s».
Во втором тесте нельзя добиться того, чтобы из двух одинаковых ограничений выполнялось ровно одно, поэтому ответ — 0.
Название |
---|