eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Прямоугольники online

Прямоугольники online

Вася нарисовал на плоскости \textbf{N} различных точек с целыми координатами. Теперь он хочет уметь быстро отвечать, а сколько точек лежит внутри заданного прямоугольника со сторонами, параллельными осям координат. \InputFile В первой строке задается количество точек \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{50000}). Последующие \textbf{N} строк содержат координаты точек\textbf{x_i} \textbf{y_i}. Следующая строка содержит число запросов \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{50000}). Следующие \textbf{M} строк содержат описания запросов, каждый в формате \textbf{x_1}, \textbf{y_1}, \textbf{x_2}, \textbf{y_2} (\textbf{0} ≤ \textbf{x_1} ≤ \textbf{x_2} ≤ \textbf{10^9}, \textbf{0} ≤ \textbf{y_1} ≤ \textbf{y_2} ≤ \textbf{10^9}). Для каждого запроса нужно сделать две вещи: \begin{itemize} \item Посчитать число точек в соответствующем прямоугольнике (включая границы). \item Все посчитанные точки стереть. \end{itemize} \OutputFile Для каждого из запросов выведите посчитанное количество точек.
Лимит времени 3 секунды
Лимит использования памяти 64 MiB
Входные данные #1
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
3
0 0 1 1
0 0 2 2
0 0 3 3
Выходные данные #1
4
5
0