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 Hi stories (1 ≤ Hi ≤ 109), and is occupied by Ci citizens (1 ≤ Ci ≤ 109).
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, Xi, Li, and Ri (0 ≤ Xi ≤ N; 1 ≤ Li ≤ Ri ≤ N). It consists of two phases, as follows:
- 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 Xi times, meaning that exactly Xi skyscrapers will get vaporized in this phase.
- The beam will vaporize all of the un-vaporized skyscrapers numbered between Li and Ri, inclusive. Note that some of these skyscrapers may have already been vaporized in phase 1 of the attack, meaning that anywhere between 0 and Ri − Li + 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.
In test cases worth 7/26 of the points, N ≤ 2000, M ≤ 2000, and Hi = 1 for each i.
In test cases worth another 6/26 of the points, N ≤ 2000 and M ≤ 2000.
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, Hi and Ci, 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, Xi, Li, and Ri, for i = 1..M.
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−5 absolute or relative error compared to the judge's answer to be considered correct.
5 4 1 2 50 6 400 4 100 3 33 3 5 1 5 4 2 2 2 2 4
584.0 584.0 550.5
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).
Point Value: 17 (partial)
Time Limit: 5.00s
Memory Limit: 64M
Added: May 13, 2018
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3