Для каждого момента i времени запомним количество сообщений z[i], которое нужно отправить в момент времени i. Теперь пройдем по каждому моменту времени от 1 до 106, поддерживая текущий размер очереди sz. На каждой итерации попробуем уменьшить размер очереди на 1, то есть выполним sz = max(sz - 1, 0), затем прибавим сообщения, которые нужно отправить в эту секунду, то есть выполним sz = sz + z[i]. На каждом шаге будем обновлять максимальное значение очереди и текущее время, если sz > 0. После выполнения цикла, если в очереди остались неотправленные сообщения, то нужно еще раз обновить ответ.
В этой задаче нужно было посчитать степени каждой вершины и найти ответ. Замечу, поскольку n > = 4, m > = 3 и граф связный, то ответ однозначный.
1) все степени 2 и у двух вершин степень 1 — шина.
2) все степени 2 — кольцо
3) все степени 1 и у одной степень > 2 — звезда
4) иначе неизвестно
Задача решается перебором. Для начала переберем сколько цифр в каждом четверти мы возьмем, например AAA.B.CC.DDD. Теперь посчитаем количество символов в этой строке (AAABCCDDD) и переберем цифры на первой половине этой строки (поскольку строка должна быть палиндромом, то вторая половина однозначно восстанавливается). После этого проверим, что такой ip-адрес является корректным и содержит правильный набор цифр. Если ip-адрес удовлетворяет всем условиям задачи, то добавим его к ответу.
Ограничения в задаче были не слишком удачными и провоцировали писать решение за квадрат, мы постарались максимально не позволить таким решениям пройти.
У этой задачи много правильных решений. Изначально планировалось решение, которое предподсчитывает частичные dsu (структура данных disjoint set union) на префиксах и на суффиксах, то есть массивы ldsu[M][N] и rdsu[M][N]. После этого на запрос [lf ; rg] легко ответить за время O(N·A - 1), если объединить множества ldsu[lf - 1] и rdsu[rg + 1], где A - 1 -- обратная функция Аккермана (константа от dsu).
У этой задачи много правильных решений. Изначально предполагалось решение, использующие корневую эвристику. Разобьем все запросы на sqrt(m) блоков. Будем поддерживать текущий массив b в виде отрезков в массиве z, который хранит четверки (lf, rg, type, start), где lf, rg — отрезок индексов массива b, type — 0 или 1, означающее из какого массива взяты числа для этого отрезка, start — позиция начала этого отрезка в массиве типа type.
На запросы будем отвечать в тупую, то есть честно пересчитывать как изменится массив z от запроса копирования и отвечать на запросы значения в позициях. Однако, каждые sqrt(m) запросов будем сливать данные из массива z в массив b, для того чтобы сам массив z сильно не разрастался.
Есть простое решение с деревом отрезков, которое умеет делать покраску на отрезке. Пусть пришел запрос копирования [lf ; rg], , тогда покрасим отрезок запроса [lf ; rg] в цвет, равный номеру запросу. Все запросы будем сохранять. Пусть пришел запрос значения в позиции x, тогда найдем цвет в дереве в этой позиции. Если такого цвета нет, значит мы находимся в исходном массиве b (выведем b[x]), иначе посчитаем смещение dx от начала этого запроса до нашей позиции x и выведем a[x + dx].
can someone translate tutorial of 292-D in english
English Translation-
The restrictions in the problem were not very successful and provoked a solution to be written in a square; we tried not to let such solutions pass as much as possible.
This task has many correct solutions. Initially, a solution was planned that calculates partial dsu (data structure disjoint set union) on prefixes and suffixes, that is, arrays ldsu [ M ] [ N ] and rdsu [ M ] [ N ] . After that, the request [ lf ; rg ] it is easy to answer in time O ( N · A - 1 ) if we combine the sets ldsu [ lf - 1] and rdsu [ rg + 1] , where A - 1 is the inverse Ackerman function (constant from dsu).
Thanks, it helped a lot
I didn't understand the 292E (copy data) solution. Can someone help me out.
u r gray why do you try to understand complex problems