DMOPC '18 Contest 6 P5 - Quadrat Sampling

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 256M

Problem type

Renowned scientist Dr. Henri has just returned from an expedition to Algonquin Park to document the sizes of various animal populations. Unfortunately, he has forgotten to study the most important animal of all: the Canada goose!

As Dr. Henri does not have time to go back to the park, he decides to take a satellite image of it and count the geese in the image instead. Algonquin Park can be represented as a grid of N rows and M columns. There are K geese in the park, the i-th of which is located at row a_i and column b_i. Multiple geese may be at the same location.

Of course, it would be too time-consuming to count every single goose in the image. So, Dr. Henri will use a method called quadrat sampling. He will choose Q rectangles, or quadrats, the i-th of which has its top left corner at (r_{1i}, c_{1i}) and its bottom right corner at (r_{2i}, c_{2i}). Then, he will define the raw total as the sum of the number of geese within quadrat i over all i from 1 to Q. He can then use this total to estimate the size of the goose population.

However, the geese have gotten wind of Dr. Henri's plan! They know that Dr. Henri will take the satellite image in exactly T minutes from now, and they also know the positions of the Q quadrats.

In an attempt to make their population seem larger and even more terrifying, each goose may choose to fly to a new position. A goose can fly at the speed of one cell per minute, and in order to save time, each goose will fly along only one of the four cardinal directions, without turning. The geese want to maximize the raw total obtained by Dr. Henri.

What is the largest raw total obtainable?


1 \le N, M \le 10^9
1 \le K, Q \le 100\,000
0 \le T \le 10^9
1 \le a_i \le N
1 \le r_{1i} \le r_{2i} \le N
1 \le b_i \le M
1 \le c_{1i} \le c_{2i} \le M

Subtask 1 [20%]

1 \le N, M, K \le 2\,000

Subtask 2 [40%]

1 \le N, M \le 100\,000

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line will contain five space-separated integers, N, M, K, Q, and T.
The next K lines will each contain two space-separated integers, a_i and b_i, the location of the i-th goose.
The next Q lines will each contain four space-separated integers, r_{1i}, c_{1i}, r_{2i}, and c_{2i}, the position of the i-th quadrat.

Output Specification

Output one integer, the raw total that Dr. Henri will obtain if the geese choose their positions optimally.

Sample Input 1

5 5 3 2 2
1 3
4 1
3 4
1 3 3 5
3 2 4 4

Sample Output 1


Explanation for Sample 1

If goose 1 flies downward to (3, 3), goose 2 flies rightward to (4, 2), and goose 3 stays put, Dr. Henri will count 2 geese in quadrat 1 and 3 geese in quadrat 2 for a raw total of 5 geese.

Sample Input 2

5 5 3 2 0
1 3
4 1
3 4
1 3 3 5
3 2 4 4

Sample Output 2


Explanation for Sample 2

The geese do not have time to move at all, so Dr. Henri will count 2 geese in quadrat 1 and 1 goose in quadrat 2 for a raw total of 3 geese.


There are no comments at the moment.