Akezhan_Askar

Помогите понять почему у меня WA на 15 тесте. Проходит только на 60 баллов.
Идея проста, создаю два дерева отрезков.
Первая хранит в себе самую высокую точку на оси Y на каком то отрезке на оси X
Вторая хранит в себе количество занятых квадратов на высоте Y
Вот код

Elnar_Niyazbek

(запись удалена автором)

shkhn

В остальных подзадачах, что у тебя не прошло y\leq 10^{9}. Размер ДОшки для высот ты делаешь равным 2^{n}, а log_{2}10^{9}\approx 2^{30}. Массив размером в 2^{30} ты не сможешь сделать, из-за переполнения.

Решить на 100 можно с помощью:

1. Неявное Дерево Отрезков
2. Сжатие координат

1 ответ

Akezhan_Askar

Почему тогда у меня WA если должен быть ML. И плюс у меня то не массив создается а unordered map

Akezhan_Askar

У меня фейлится на 5 подтесте где y <= 1e6

shkhn

ty.add(top + 1, top + h + 1, r - l + 1);

Если h = 10^{9} и t = 10^{9}, у тебя не будет здесь проблем с памятью?

1 ответ

Akezhan_Askar

Стой у меня же с каждым запросом создается
log y вершин в итоге выйдет qlogy памяти.

upd: проблема была в том что у меня int переполнялся и все…

shkhn

Помогите с решением задачи с области

Zhabka

Подсказка 1:

Подсказка 2:

Подсказка 3:

Подсказка 4:

Подсказка 5:

kourai

А откуда не подскажите можно взять задачи с области/респы для информатиков?

1 ответ

Zhabka

matol или группы в кфе

1 ответ

kourai

что такое кфе? (я не ифнорматик, спрашиваю для друга)

1 ответ

Zhabka

1 ответ

kourai

хахахха, буду знать что это сокращенно

Beka

почему после бинарного поиска мы в ответу прибавляем L то есть максимальный размер квадрата для верхней границы квадрата? Ведь в квадрате (i, j, i+L-1, j+L-1) ровно L^2 подматриц

1 ответ

shkhn

Подматрица != квадрат. Заметим, что мы использовали здесь бин поиск для того, чтобы понять, какой максимальный квадрат может быть, если нашим верхним левым будет [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.