10457: Скільком прямокутникам належить точка?
Відправити розв'язок
Бали:
100 (partial)
Time limit:
2.0s
Memory limit:
256M
Author:
Problem type
Allowed languages
Brain****, C++, Java, Pascal, Python, v8js
На площині задано \(N\) прямокутників зі сторонами паралельними осям координат, і \(M\) точок. Для кожної точки визначіть скільком прямокутникам вона належить (якщо точка лежить на границі прямокутника, вона теж рахується)
Формат вхідних даних
В першому рядку число \(N\) - кількість прямокутників (\(1 \le N \le 2*10^5\))
В наступних \(N\) рядках по 4 цілих числа \(X1,Y1\) - координати лівого нижнього, та \(X2,Y2\) - координати правого верхнього кутів прямокутника. (\(0 \le X1,Y1,X2,Y2 \le 10^6\))
В першому рядку число \(M\) - кількість точок (\(1 \le M \le 2*10^5\))
В наступних \(M\) рядках по 2 цілих числа \(X,Y\) - координати відповідної точки (\(0 \le X,Y \le 10^6\))
Формат вихідних даних
Для кожної точки виведіть в окремому рядку скільком прямокутникам вона належить.
Приклад вхідних даних
2
10 20 30 40
20 10 40 30
8
10 30
15 30
20 30
35 30
30 30
35 30
40 30
50 30
Приклад вихідних даних
1
1
2
1
2
1
1
0
Коментарі