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 B_i (−10⁹ ≤ B_i ≤ 10⁹). There are also M (1 ≤ M ≤ 300,000) agents stationed along the street, with the i-th one at position A_i (−10⁹ ≤ A_i ≤ 10⁹). All N + M of these positions are distinct. Agent i has a sight range of R_i (1 ≤ R_i ≤ 10⁹), meaning that they're able to keep watch over all buildings at positions in the inclusive range of positions [A_i − R_i, A_i + R_i]. 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 2ⁱ 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 C_i (1 ≤ C_i ≤ 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 C_i agents, you should output −1 instead. Otherwise, the total cost (in dollars) may be quite large, so you only need to output it modulo 10⁹ + 7.

Subtasks

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.

Input Format

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 B_i, for i = 1..N.
The next M lines each consist of two space-separated integers A_i and R_i, for i = 1..M.
The next Q lines each consist of a single integer C_i, for i = 1..Q.

Output Format

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 10⁹ + 7) or −1 if it's impossible.

Sample Input

2 4 3
10
20
14 5
22 11
0 1
15 5
1
2
3

Sample Output

6
22
-1

Explanation

If M hires agents 1 and 2 (for a cost of 2¹ + 2² = 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.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 7.00s
Memory Limit: 64M
Added: Apr 08, 2016
Author: SourSpinach

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

Comments (Search)