Woburn Challenge 2017-18 Finals Round - Senior Division

Problem 4: Ultimatum

The Party of Extraterrestrial Gangsters are not at all pleased with how their invasion of Earth is going so far. Their soldiers on the ground are losing in combat to the well-prepared battalions of cows and monkeys, and their nuclear bomb has been defused with particular ease. Fortunately for them, PEG's space battleship is also outfitted with an enormously powerful vaporizer beam capable of wiping out Scarberia in an instant. The PEG leaders were hoping to avoid resorting to such a merciless tactic, but they're running out of alternatives. However, before proceeding with any vaporization, they'll issue an ultimatum to the Scarberian leaders, detailing the amount of potential destruction and providing an opportunity for unconditional surrender instead.

Downtown Scarberia has a row of N (1 ≤ N ≤ 200,000) skyscrapers, numbered 1 to N from left to right. Skyscraper i has a height of H_i stories (1 ≤ H_i ≤ 10⁹), and is occupied by C_i citizens (1 ≤ C_i ≤ 10⁹).

The PEG leaders have come up with a list of M (1 ≤ M ≤ 200,000) possible plans of attack using their vaporizer beam. The i-th plan is defined by three integers, X_i, L_i, and R_i (0 ≤ X_i ≤ N; 1 ≤ L_i ≤ R_i ≤ N). It consists of two phases, as follows:

1. The beam will lock onto the tallest remaining un-vaporized skyscraper, and vaporize it. If there are multiple such skyscrapers with equal heights, they'll choose one of them uniformly at random. They'll repeat this process X_i times, meaning that exactly X_i skyscrapers will get vaporized in this phase.
2. The beam will vaporize all of the un-vaporized skyscrapers numbered between L_i and R_i, inclusive. Note that some of these skyscrapers may have already been vaporized in phase 1 of the attack, meaning that anywhere between 0 and R_i − L_i + 1 skyscrapers (inclusive) will get vaporized in this phase.

For each possible plan of attack, the PEG leaders are interested in the expected number of citizens who would get vaporized in it (that is, the expected total number of citizens occupying all of the vaporized skyscrapers). Disclosing these statistics in an ultimatum would be sure to drive the Scarberian forces to immediately surrender! Help them determine this value for each of the M plans of attack. Note that none of the plans will actually be executed (yet), meaning that no vaporization will carry over between them.

Subtasks

In test cases worth 7/26 of the points, N ≤ 2000, M ≤ 2000, and H_i = 1 for each i.
In test cases worth another 6/26 of the points, N ≤ 2000 and M ≤ 2000.

Input Format

The first line of input consists of a single integer, N.
N lines follow, the i-th of which consists of two space-separated integers, H_i and C_i, for i = 1..N.
The next line consists of a single integer, M.
M lines follow, the i-th of which consists of three space-separated integers, X_i, L_i, and R_i, for i = 1..M.

Output Format

Output M lines, the i-th of which contains a single real number, the expected number citizens who would get vaporized in the i-th plan of attack.
Your answer must have at most 10⁻⁵ absolute or relative error compared to the judge's answer to be considered correct.

Sample Input

5
4 1
2 50
6 400
4 100
3 33
3
5 1 5
4 2 2
2 2 4

Sample Output

584.0
584.0
550.5

Sample Explanation

In the first plan of attack, all 5 skyscrapers would already get vaporized in the first phase.

In the second plan of attack, the 4 tallest skyscrapers would get vaporized in the first phase, leaving just skyscraper 2 behind, which would happen to get targeted in the second phase anyway.

In the third plan of attack, phase 1 would involve vaporizing skyscraper 3 followed by either skyscraper 1 or 4, with 50% probability each. In the end, either 550 or 551 citizens would be vaporized, with 50% probability each (depending on the skyscraper chosen in phase 1).

All Submissions
Best Solutions

Point Value: 17 (partial)
Time Limit: 5.00s
Memory Limit: 64M
Added: May 13, 2018
Author: SourSpinach

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

Comments (Search)