Woburn Challenge 2016-17 Round 2 - Senior Division

Problem 4: Diplomacy

Having run low on dilithium, the Enterprise has stopped at an isolated space station to refuel. The station is inhabited by N (1 ≤ N ≤ 200,000) humanoids of various races. Unfortunately, it seems that their differences have been creating an increasingly heated conflict. In particular, there are constant debates over the station's artificial environmental settings! Some species prefer a warmer environment than others, or one with a stronger gravitational force. Though this might seem like a trivial matter, the frequent changing back and forth of the environmental settings appears to pose a serious threat to the state of tentative peace aboard the station, with threats of violent conflict in the air.

As a neutral third party, it'll be up to the crew of the Enterprise to step in and make a fair decision. The Enterprise's ambassador, Neelex, has been entrusted with selecting environmental settings in a neutral fashion, with the space station's residents agreeing to abide by his decision. However, if he makes a poor decision, there could still be serious trouble!

Two aspects of the space station's environmental settings may be set – its temperature (in degrees Celsius) and its gravity (in m/s²). Each of these values may be set to any positive integer. The i-th humanoid aboard the station would like the temperature to be anywhere between A_i and B_i (1 ≤ A_i ≤ B_i ≤ 10⁹), inclusive, and the gravity to be anywhere between C_i and D_i (1 ≤ C_i ≤ D_i ≤ 10⁹), inclusive. They'll only be content if both the temperature and the gravity lie within their requested ranges (they don't care if only one of their requests is satisfied).

Neelex may not be able to choose a set of environmental settings to leave everyone happy, but he'd like to get as close to that as possible, in order to minimize the chance of a dispute. What's the maximum number of humanoids that can be satisfied by any possible choice of temperature and gravity settings?

In test cases worth 4/38 of the points, B_i ≤ 200, D_i ≤ 200, and N ≤ 200.
In test cases worth another 6/38 of the points, N ≤ 200.
In test cases worth another 10/38 of the points, N ≤ 2000.

Input Format

The first line of input consists of a single integer N.
N lines follow, the i-th of which consists of four space-separated integers A_i, B_i, C_i, and D_i (for i = 1..N).

Output Format

Output a single integer – the maximum number of humanoids that can be simultaneously satisfied.

Sample Input

4
64 100 35 55
100 200 10 40
111 190 39 69
12 120 38 38

Sample Output

3

Explanation

The first, second, and fourth humanoids will all be satisfied if the temperature is set to 100 and the gravity is set to 38. Any other configuration results in at most two humanoids being satisfied.

All Submissions
Best Solutions

Point Value: 17 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Added: Dec 11, 2016
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)