Третий раунд SnarkNews Winter Series 2017 заканчивается 24 января в 14:00 (то есть меньше, чем через сутки). Как и несколько предыдущих серий, SNWS-2017 проходит на системе Яндекс.Контест. Опубликовано расписание серии. Начать участие в серии можно с любого раунда.
По просьбам участников отдельно публикую ссылку на вход в раунд. Здесь же по окончании раунда в соответствии с расписанием можно будет обсудить задачи первого раунда.
P.S. Четвёртый раунд уже стартовал.









Как решать B?
Сожмём координаты, по a и по b, будем хранить дерево отрезков по a, в каждой вершине отсортированный массив возможных b-шек и дерево отрезков по b (но только те, которые реально возможны). Считаем
, памяти
.
dp[i] = max(0, max(dp[i][j] | 0 <= j < i, a[j] >= a[i] && b[j] <= b[i])) + 1— делаем запрос максимума на прямоугольнике (то есть в каждой вершине дерева по одному измерению делаем запрос максимума по другому, а границы находим с помощью отсортированного массива) и изменение значения в точке(a[i], b[i])наdp[i]. ВремениНемного кривой код.
Можно немного уменьшить страдания (и время работы), если заметить, что запросы в вершине дерева отрезков префиксные и хранить в каждой вершине дерева отрезков дерево Фенвика.
Еще можно вместо дерева отрезков для a делать sqrt-декомпозицию, внутри каждого блока которой хранить уже дерево отрезков.