Rectangle Land

In rectangle land, everything is a rectangle (parallel to $x$ axis and parallel to $y$ axis) and all coordinates are integers. The laws of physics are strange in rectangle land – each cell phone tower provides signal coverage in the form of a rectangle with a particular signal strength. If two signal coverages (which are rectangles) overlap, then the signal coverage in the overlapped region is the sum of the signal of each rectangle.

In rectangle land, there is an evil telecommunication company known as Z Inc which charges people according to the signal strength of the location (the larger the signal strength, the less you pay for the cell phone signal). Victor lives in rectangle land and would like to find the maximum signal coverage that he can get (so that he can pay less) and also what is the area of regions with maximum signal coverage. This task aims to help Victor to answer this question!


The input consists of one line with one integer $C$ ($1 \leq C \leq 5$), the number of test cases. This is followed by $C$ test cases. Each test case consist of:

  • One line with one integer $n$ ($1 \leq n \leq 100\, 000$).

  • $n$ lines, each line contains 5 integers $x_1$, $y_1$, $x_2$, $y_2$ and $s$ ($x_1 \le x_2$, $y_1 \le y_2$, $-1\, 000\, 000 \leq x_1, y_1, x_2, y_2 \leq 1\, 000\, 000$, $1 \le s \le 10\, 000)$ which describes a cell phone tower with a rectangle of $(x_1, y_1)$ and $(x_2, y_2)$ and signal strength $s$.


For each test case, output one line that contains two integers separated by a single space: the max signal coverage and then the area

Sample Input 1 Sample Output 1
0 3 4 6 1
1 4 6 8 2
2 0 8 5 3
0 0 1000 1000 7
6 2
7 1000000
CPU Time limit 7 seconds
Memory limit 1024 MB
Difficulty 7.4hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in