Woburn Challenge 2015-16 Round 4 - Senior Division
Problem 4: Stakeout
MI6 has received intelligence that members of the evil Spectre organization may be holding a gathering somewhere along a certain street in London. Unfortunately, they're not sure exactly in which building this gathering will take place. As such, they'll need to recruit some agents to stake out the street and look for suspicious acitivity.
The street can be represented by a number line. There are N (1 ≤ N ≤ 300,000) suspicious buildings which must be monitored, with the i-th one at position Bi (−109 ≤ Bi ≤ 109). There are also M (1 ≤ M ≤ 300,000) agents stationed along the street, with the i-th one at position Ai (−109 ≤ Ai ≤ 109). All N + M of these positions are distinct. Agent i has a sight range of Ri (1 ≤ Ri ≤ 109), meaning that they're able to keep watch over all buildings at positions in the inclusive range of positions [Ai − Ri, Ai + Ri]. Times are tough at MI6, with the agents not even willing to take this assignment for free – M will have to pay agent i a fee of 2i dollars to stay at their post, otherwise they'll get bored of the stakeout and go out for some steak instead.
In light of this monetary issue, M will need to decide on a tradeoff between cost and thoroughness. A hired agent can successfully keep an eye on all buildings in his range simultaneously, but it might not be sufficient to have each building only be watched by a single agent, in case they're taken out. As such, M would like to ask himself Q (1 ≤ Q ≤ 10) questions, with the i-th one asking "What's the minimum cost to hire agents such that each suspicious building is in sight of at least Ci (1 ≤ Ci ≤ M) of them, if this is possible at all?". Can you help M answer each of these questions, for the sake of the MI6 fundraising department? If it's impossible to have each building covered by at least Ci agents, you should output −1 instead. Otherwise, the total cost (in dollars) may be quite large, so you only need to output it modulo 109 + 7.
In test cases worth 4/35 of the points, N ≤ 10 and M ≤ 10.
In test cases worth another 5/35 of the points, N ≤ 100 and M ≤ 100.
In test cases worth another 8/35 of the points, N ≤ 2000 and M ≤ 2000.
The first line of input consists of three space-separated integers N, M, and Q.
The next N lines each consist of a single integer Bi, for i = 1..N.
The next M lines each consist of two space-separated integers Ai and Ri, for i = 1..M.
The next Q lines each consist of a single integer Ci, for i = 1..Q.
Output Q lines, one integer per line. The i-th line (for i = 1..Q) should consist of the answer to the i-th query (modulo 109 + 7) or −1 if it's impossible.
2 4 3 10 20 14 5 22 11 0 1 15 5 1 2 3
6 22 -1
If M hires agents 1 and 2 (for a cost of 21 + 22 = 6 dollars), each building will be in sight of a single agent, which is just enough to satisfy the first question. Hiring agents 1, 2, and 4 will allow each building to be in sight of at least two agents. It's impossible to have each building be in sight of three or more agents.
Point Value: 20 (partial)
Time Limit: 7.00s
Memory Limit: 64M
Added: Apr 08, 2016
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3