Настройки поиска

http://acm.sgu.ru/problem.php?contest=0&problem=394

Кратко о задаче
Во входных данных задаются координаты пиццерий и их зоны охвата. Пиццерии располагаются на плоскости в виде перевернутых на 45 градусов квадратов. Задается число K. Если наша пиццерия находится в зоне действия K или более других пиццерий, то мы ее закрываем. Вывести порядковые номера закрытых пиццерий.

На разборах Southern Subregion 2008 предлагался следующий алгоритм решения.
1. Перевернуть систему координат на 45 градусов и увеличить на корень из 2 все значения координат и длин. (в таком случае они остаются целые).
2. Добавить в массив событий следующие события: квадрат начался, закончился, проверить координату пиццерии. Отсортировать события по координате Х.
3. Пройти по массиву событий (метод сканирующей прямой) и при этом началу квадрата y1 делать операцию "+1", концу y2 "-1" в неком массиве Y. Чтобы узнать количество пиццерий покрывающих данную предлагалось суммировать значения массива от 0 до y0. (y0- координата пиццерии)

В задаче 0<y<10^9. При перевороте системы он еще увеличится.
Просто тупо создать такой большой массив не пройдет по памяти. Пробовал за место массива пользоваться map stl в c++. Все мои реализации не проходили дальше 11 теста.
Прошу помощи и подсказок по решению этой задачи.