В парке города Питсбурга есть чудесная аллея, состоящая из N посаженных в один ряд деревьев, каждое одного из K сортов. В связи с тем, что Питсбург принимает открытый чемпионат Байтландии по программированию, было решено построить огромную арену для проведения соревнований. Так, согласно этому плану вся аллея подлежала вырубке. Однако министерство деревьев и кустов воспротивилось этому решению, и потребовало оставить некоторые из деревьев в покое. Согласно новому плану строительства все деревья, которые не будут вырублены, должны образовывать один непрерывный отрезок, являющийся подотрезком исходного. Каждого из K видов деревьев требуется сохранить хотя бы по одному экземпляру. На вас возложена задача найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям.
Входные данные
В первой строке входного файла находятся два числа N и K ( 1 ≤ N , K ≤ 250000 ). Во второй строке входного файла следуют N чисел (разделенных пробелами), i -ое число второй строки задает цвет i -ого слева дерева в аллее. Гарантируется, что присутствует хотя бы одно дерево каждого цвета
Выходные данные
В выходной файл выведите два числа, координаты левого и правого концов отрезка минимальной длины, удовлетворяющего условию. Если оптимальных ответов несколько, выведите любой.
Примеры
входные данные
5 3
1 2 1 3 2
выходные данные
2 4
входные данные
6 4
2 4 2 3 3 1
выходные данные
2 6

Предыдущий
вопрос Следующий
вопрос

Question

В парке города Питсбурга есть чудесная аллея, состоящая из N посаженных в один ряд деревьев, каждое одного из K сортов. В связи с тем, что Питсбург принимает открытый чемпионат Байтландии по программированию, было решено построить огромную арену для проведения соревнований. Так, согласно этому плану вся аллея подлежала вырубке. Однако министерство деревьев и кустов воспротивилось этому решению, и потребовало оставить некоторые из деревьев в покое. Согласно новому плану строительства все деревья, которые не будут вырублены, должны образовывать один непрерывный отрезок, являющийся подотрезком исходного. Каждого из K видов деревьев требуется сохранить хотя бы по одному экземпляру. На вас возложена задача найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям.
Входные данные
В первой строке входного файла находятся два числа N и K ( 1 ≤ N , K ≤ 250000 ). Во второй строке входного файла следуют N чисел (разделенных пробелами), i -ое число второй строки задает цвет i -ого слева дерева в аллее. Гарантируется, что присутствует хотя бы одно дерево каждого цвета
Выходные данные
В выходной файл выведите два числа, координаты левого и правого концов отрезка минимальной длины, удовлетворяющего условию. Если оптимальных ответов несколько, выведите любой.
Примеры
входные данные
5 3
1 2 1 3 2
выходные данные
2 4
входные данные
6 4
2 4 2 3 3 1
выходные данные
2 6

Предыдущий
вопрос Следующий
вопрос

eva

31 Июл 2019 в 19:41

800 +1

1

Helper · Answer 1

include include include include

int main() {
int N, K;
std::cin >> N >> K;

std::vector<int> colors(N);
for (int i = 0; i < N; ++i) {
std::cin >> colors[i];
}
std::unordered_map<int, int> colorCount;
int uniqueColors = 0;
int left = 0, right = 0;
int minLength = std::numeric_limits<int>::max();
for (; right < N; ++right) {
if (colorCount[colors[right]] == 0) {
uniqueColors++;
}
colorCount[colors[right]]++;
while (uniqueColors == K) {
if (right - left < minLength) {
minLength = right - left;
// Update the indices
leftMin = left;
rightMin = right;
}
colorCount[colors[left]]--;
if (colorCount[colors[left]] == 0) {
uniqueColors--;
}
left++;
}
}
std::cout << leftMin + 1 << " " << rightMin + 1 << std::endl;
return 0;

}