![]() |
||||||||||
|
||||||||||
Operation HopeTime Limit: 10000/10000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 495 Accepted Submission(s): 161 Problem Description Little Q is playing an RPG online game. In this game, there are $n$ characters labeled by $1,2,\dots,n$. The $i$-th character has three types of quotas: - $a_i$ - The maximum points of damage he can achieve in $15$ seconds. - $b_i$ - The maximum points of damage he can achieve in $40$ seconds. - $c_i$ - The maximum points of damage he can achieve in $120$ seconds. You are the team leader working for the new balance between these $n$ characters, aiming at bringing hope to the weak characters. For each character, your teammates have made a plan to strengthen some skills such that the three quotas may be increased as a result. Note that it is not allowed to weaken characters, because it will make their owners upset. To make a perfect balance, you need to accept some plans and deny others such that the gap between all the $n$ characters is minimized. Note that a plan can only be entirely accepted or entirely denied. Here, the gap is defined as $$ \max(\max_{1\leq i\leq n}a_i-\min_{1\leq i\leq n}a_i, \max_{1\leq i\leq n}b_i-\min_{1\leq i\leq n}b_i, \max_{1\leq i\leq n}c_i-\min_{1\leq i\leq n}c_i) $$ Input The first line contains a single integer $T$ ($1 \leq T \leq 100$), the number of test cases. For each test case: The first line contains a single integer $n$ ($1 \leq n \leq 100\,000$), denoting the number of characters. In the next $n$ lines, the $i$-th line contains six integers $a_i$, $b_i$, $c_i$, $a_i'$, $b_i'$ and $c_i'$ ($1\leq a_i\leq a_i'\leq 10^9$, $1\leq b_i\leq b_i'\leq 10^9$, $1\leq c_i\leq c_i'\leq 10^9$), describing the quotas of the $i$-th character now and in plan. It is guaranteed that the sum of all $n$ is at most $500\,000$. Output For each test case, output a single line containing an integer, denoting the optimal gap. Sample Input
Sample Output
Source | ||||||||||
|