I Hate Ready to Program P9 - Console Compilation

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.5s
Memory limit: 512M

Problem type

As you try to add some graphics for a splash screen, you notice that RtP does not execute your program sometimes! As you slowly pull your hair out on trying to figure out the issue, a classmate tells you that the reason why your program isn't running is that some pixels have too many draw commands on that pixel!

The console is N by M pixels, with N columns and M rows, where (1,1) is the top-left corner and (N,M) is the bottom-right corner. You have drawn K rectangles, each with the top-left corner at row x_i and column y_i, as well as width w_i and height h_i. Your friend has looked at your console and given you Q queries. For each query, similarly to the input of the rectangles drawn, you are given the top-left corner and the width and height of the rectangle. In this rectangle, you want to find the number of pixels that have more than R rectangles drawn over that pixel in the rectangular query.


1 \leq N,M,K,Q \leq 5\times 10^3

1 \leq x_i,w_i < N

1 \leq y_i,h_i < M

1 \leq R \leq 500

Subtask 1 [30%]

1 \leq N,M,K,Q \leq 100

1 \leq R \leq 25

Subtask 2 [70%]

No further constraints.

Input Specification

The first line will contain space-separated integers N,M,K,Q,R.

The next K lines will contain space-separated integers x_i,w_i,y_i,h_i.

The next Q lines will contain space-separated integers x_i,w_i,y_i,h_i.

Output Specification

Output R lines, the number of pixels that have at least R rectangles drawn over it.

Sample Input

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

Sample Output


Sample Explanation

The points (2,2), (2,3), (3,2), (3,3), (4,4), (4,5), (5,4), and (5,5) have at least 3 overlapping rectangles.

Here is a diagram of the squares:


There are no comments at the moment.