Решаю задачу из Открытой олимпиады 2014-2015 года, если кому интересно, вот условие и разбор, задача последняя и в условиях, и в разборе. Путем некоторых хитрых преобразований задача была сведена к следующей, если я правильно понял: дана координатная плоскость, и какие-то координаты на одной оси, и какие-то координаты на другой. На пересечении всех этих координат находятся наши точки. Далее дано несколько прямоугольников, и надо найти точку, накрытую наибольшим числом прямоугольников. Решение с двумерным деревом отрезков/Фенвика довольно очевидно, но есть более быстрое решение с одномерным деревом и сканирующей прямой. В сканирующей прямой я пока разбираюсь слабо, поэтому не очень понимаю, как это именно реализовывать. Буду благодарен за помощь. :)

Не раз вижу, что для использования какого-нибудь алгоритма, имеющего дело с большими числами, нужно предварительно сжать эти числа, однако поиск самого алгоритма сжатия ничего не дал. Правильно ли я понимаю, что для этого нужно создать массив пар <число, ссылка на число в прежнем массиве>, отсортировать его и по порядку перенумеровать числа с 1?

Не могу нигде найти, какие опции компилятора g++ 6.2 установлены на codeforces. Сейчас мучаюсь с этим компилятором на другом сайте и пытаюсь понять, в чём отличия тамошней версии от здешней. Буду очень благодарен за помощь.

Не могу понять разбор задачи E из ИОИП прошлого года. Условия задач — http://neerc.ifmo.ru/school/ioip/problems-2016.pdf Разбор — http://neerc.ifmo.ru/school/io/archive/20160327/analysis-20160327-individual.pdf Мне понятно всё до последнего слайда. Вопрос номер один: в разборе утверждается, что при решении задачи для отрезка [0; 2d + 1] задачу можно будет легко решить и для остальных позиций путем проставления 0 и 1 в соответствии с их классом эквивалентности. Но почему не может возникнуть ситуации, когда такое проставление не даст корректного ответа для других отрезков(то есть сумма там не будет равняться требуемой)?

Первый вопрос снимается, если ответить на второй: в последнем пункте говорится, что cj равны между собой, то есть в отрезке [0; 2d + 1] у нас одинаковое количество непроставленных элементов для каждого класса эквивалентности. Действительно, тогда в других отрезках эти числа тоже будут одинаковыми и мы получим ответ на первый вопрос. Но каким образом можно доказать или хотя бы обнаружить это свойство? По-моему это утверждение совсем не очевидно.

Если у кого-нибудь есть другие идеи по поводу этой задачи, буду очень благодарен, если вы их озвучите).

Update: Кажется, стало немного понятнее, но до конца не уверен.

What is the best for Dijkstra's algorithm: set with erasing of the vertices adjacent to the current one and the subsequent insertion of them with the new values or a priority_queue with a lot of irrelevant vertices? Or maybe some other approach using std?

Почему в соревнованиях можно смотреть тесты, а в тренировках нельзя? По-моему это немного странно. Пытаюсь сейчас решить последнюю задачу из Технокубка Раунд 1, вроде бы всё работает, тесты из соревнований проходят, а сдать задачу не могу. Неужели в тренировках и соревнованиях разные тесты для одной и той же задачи?