Информатика → Областная → 2021
Это обсуждение публикации https://olympiads.bc-pf.org/informatics/oblast/2021
Это обсуждение публикации https://olympiads.bc-pf.org/informatics/oblast/2021
Помогите понять почему у меня WA на 15 тесте. Проходит только на 60 баллов.
Идея проста, создаю два дерева отрезков.
Первая хранит в себе самую высокую точку на оси Y на каком то отрезке на оси X
Вторая хранит в себе количество занятых квадратов на высоте Y
Вот код
2 лайка
(запись удалена автором)
В остальных подзадачах, что у тебя не прошло y\leq 10^{9}. Размер ДОшки для высот ты делаешь равным 2^{n}, а log_{2}10^{9}\approx 2^{30}. Массив размером в 2^{30} ты не сможешь сделать, из-за переполнения.
Решить на 100 можно с помощью:
- Неявное Дерево Отрезков
- Сжатие координат
2 лайка
Почему тогда у меня WA если должен быть ML. И плюс у меня то не массив создается а unordered map
1 лайк
У меня фейлится на 5 подтесте где y <= 1e6
2 лайка
ty.add(top + 1, top + h + 1, r - l + 1);
Если h = 10^{9} и t = 10^{9}, у тебя не будет здесь проблем с памятью?
Стой у меня же с каждым запросом создается
log y вершин в итоге выйдет qlogy памяти.
upd: проблема была в том что у меня int переполнялся и все…
1 лайк
Подсказка 1:
Все числа положительные
Подсказка 2:
Перебираем левую верхнюю границу квадрата.
Подсказка 3:
Сумму на квадрате быстро можно посчитать с помощью двумерных префиксных сумм.
Подсказка 4:
Если для квадрата с левой верхней границей (i, j) размера x, то для любого другого квадрата с этой же верхней границы и размером <x условие тоже будет выполняться.
Подсказка 5:
Можно использовать бинарный поиск чтобы найти максимальный размер квадрата с левой верхней границе (i, j).
9 лайков
А откуда не подскажите можно взять задачи с области/респы для информатиков?
3 лайка
matol или группы в кфе
что такое кфе? (я не ифнорматик, спрашиваю для друга)
3 лайка
1 лайк
хахахха, буду знать что это сокращенно
почему после бинарного поиска мы в ответу прибавляем L то есть максимальный размер квадрата для верхней границы квадрата? Ведь в квадрате (i, j, i+L-1, j+L-1) ровно L^2 подматриц
1 лайк
Подматрица != квадрат. Заметим, что мы использовали здесь бин поиск для того, чтобы понять, какой максимальный квадрат может быть, если нашим верхним левым будет [i, j]. То есть, если нам подходит квадрат [i + L - 1, j + L - 1], то логично, что квадраты [i + L - 2, j + L - 2], [i + L - 3, j + L - 3], … [i, j] будут также подходить (напомню, a[i] не может быть отрицательным). Таких квадратов у нас будет L штук, из-за этого мы прибавляем L.