2015-16 Woburn Challenge Finals - Senior Division

Problem 5: Supply Chain

At last, the final battle for Scarberia is upon us! The cows and monkeys have agreed that the fighting will take place on a circle of N (3 ≤ N ≤ 300,000) pastures, connected to one another in a cycle by N two-way bridges. The i-th bridge can support a weight of at most S_i (1 ≤ S_i ≤ 10⁶) pounds, and connects pastures i and i + 1 (if 1 ≤ i < N), or pastures N and 1 (if i = N).

The monkeys' base of operations is located in pasture 1, and they have troops stationed in all of the other pastures. The monkeys, being masterful makers of war, are keenly aware that the most effective soldiers are well-fed soldiers. As such, they have a convoy of M (1 ≤ M ≤ 300,000) trucks which will deliver bananas from their base daily. The i-th truck has a weight of W_i (1 ≤ W_i ≤ 10⁶) pounds, and every day, it will depart from pasture 1, driving around amongst the pastures and delivering B_i (1 ≤ B_i ≤ 10⁶) bananas to each other pasture that it can reach. Each truck can only cross bridges which can at least support its weight, and it can drive back and forth as much as necessary (even revisiting pastures multiple times), but it will only deliver a load of bananas to each pasture at most once. Therefore, each day, the i-th truck will deliver between 0 and B_i×(N − 1) bananas in total.

The battle is scheduled to last for D (1 ≤ D ≤ 300,000) days, and in order to manage their banana hoard successfully, the monkeys would like to determine how many bananas their trucks will deliver on each day. However, this aspect of the war promises to be particularly dynamic, as those dastardly cows are also well aware of the military importance of the supply chain and will attempt to sabotage it, while the monkeys will hopefully enact the necessary countermeasures. One event will occur at the start of each day (before the trucks roll out to make their deliveries, with the type of the event on the i-th day indicated by T_i (1 ≤ T_i ≤ 2):

• If T_i = 1, the cows will undermine the structural integrity of the X_i-th (1 ≤ X_i ≤ N) bridge, permanently reducing its maximum supported weight by Y_i (1 ≤ Y_i < 10⁶) pounds. It's guaranteed that it will still be able to support a weight of at least 1 pound.
• If T_i = 2, the monkeys will remodel their X_i-th (1 ≤ X_i ≤ M) truck such that it henceforth weighs Y_i (1 ≤ Y_i ≤ 10⁶) pounds. Note that this could cause its weight to increase (thanks to cows cleverly disguised as monkey mechanics).

The outcome of the entire war, and the monkeys' opportunity to reclaim Scarberia once and for all, depends on this supply chain! Can you help the monkeys determine how many bananas their trucks will deliver in total on each of the D days of the battle?

In test cases worth 6/33 of the points, N ≤ 200, M ≤ 200, and D ≤ 200.
In test cases worth another 8/33 of the points, N ≤ 2000, M ≤ 2000, and D ≤ 2000.
In test cases worth another 8/33 of the points, T_i = 1.
In test cases worth another 8/33 of the points, T_i = 2.

Input Format

The first line of input consists of three space-separated integers, N, M, and D.
N lines follow. The i-th of these lines consists of a single integer, S_i (for i = 1..N).
M lines follow. The i-th of these lines consists of two space-separated integers, W_i and B_i (for i = 1..M).
D lines follow. The i-th of these lines consists of three space-separated integers, T_i, X_i, and Y_i (for i = 1..D).

Output Format

Output D lines. The i-th line of output should consist of a single integer representing the total number of bananas delivered on the i-th day (for i = 1..D).
Note that each of these values may not fit within a 32-bit integer.

Sample Input

4 5 4
5
4
2
8
3 5
1 100
2 1
5 20
6 4
2 2 100
1 4 3
1 4 4
2 2 1

Sample Output

62
58
33
333

Explanation

On the first day, the first truck will deliver 5 bananas each to pastures 2, 3, and 4. The second truck, now weighing 100 pounds, won't deliver any bananas. The third truck will deliver 1 banana to each of those 3 pastures, the fourth will deliver 20 bananas to pastures 2 and 4, and the fifth will deliver 4 bananas to just pasture 4. The total number of bananas delivered on this day will then be 5×3 + 1×3 + 20×2 + 4×1 = 62.

All Submissions
Best Solutions

Point Value: 30 (partial)
Time Limit: 5.00s
Memory Limit: 64M
Added: May 07, 2016
Author: SourSpinach

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

Comments (Search)