2016-17 Woburn Challenge Finals Round - Senior Division

Problem 5: Bovine Grenadiers

Angus and Bessie are the most well-known grenadiers in Bo Vine's army, and they're constantly trying to out-do one another. Even on the very eve of the war's first major battle, they've ended up in an argument! On this occasion, they're fighting over how to split up the army's supply of grenades - of course, each of them wants the most powerful grenades to themselves! In an attempt at fairness, they're going to play a game to divide up the grenades.

There are N (1 ≤ N ≤ 300,000) boxes of grenades. The i-th box contains G_i (1 ≤ G_i ≤ 300,000) grenades, with the j-th of those grenades having a "grenade power" of P_{i, j} (1 ≤ P_{i, j} ≤ 10,000,000), indicating its explosive strength. There are at most 300,000 grenades in total across all of the boxes.

Angus and Bessie will take turns performing actions, with Angus going first, until each of the grenades has been taken by one of them. All N of the boxes are initially sealed. In one turn, a cow may either unseal a sealed box, or take one grenade from an unsealed box. Both cows will make optimal actions with the goal of maximizing the total grenade power of the grenades that they'll get their hands on throughout the game (and thus minimizing the total grenade power obtained by their opponent).

To make things more exciting, the entire game will actually be independently re-played M (1 ≤ M ≤ 300,000) separate times. Before the i-th time the game gets played, a single grenade will get swapped out for a slightly different one. In particular, the B_i-th grenade in the A_i-th box (1 ≤ A_i ≤ N, 1 ≤ B_i ≤ G_Ai) will be replaced with a new grenade whose grenade power is D_i (−1 ≤ D_i ≤ 1) larger than that of the removed grenade. It's guaranteed that the new grenade's power will still be positive. Each such replacement will carry over to all subsequent times the game gets played, and the new grenade itself may get replaced later on.

Help Angus and Bessie determine the outcome of their set of games by predicting how much grenade power each of them will end up with each time they play. Rather than outputting all 2M such values (the grenade power obtained by Angus and Bessie each time they play), you only need to compute the sum of Angus's M values, as well as the sum of Bessie's M values.

In test cases worth 5/32 of the points, N = 1, M ≤ 2000, and G₁ ≤ 2000.
In test cases worth another 4/32 of the points, N = 1.
In test cases worth another 6/32 of the points, N ≤ 2000, M ≤ 2000, and there are at most 2000 grenades in total.

Input Format

The first line of input consists of two space-separated integers N and M.
N lines follow, the i-th of which consists of an integer G_i, followed by a space, followed by G_i space-separated integers P_{i, 1}, …, P_{i, Gi} (for i = 1..N).
M lines follow, the i-th of which consists of three space-separated integers A_i, B_i, and D_i (for i = 1..M).

Output Format

Output a single line consisting of two space-separated integers – the total grenade power obtained by Angus and Bessie, respectively.

Sample Input

3 3
2 4 3
1 5
2 1 1
3 2 1
3 2 1
2 1 -1

Sample Output

17 29

Sample Explanation

After the first grenade replacement, assuming both cows play optimally, Angus will end up obtaining 5 grenade power (for example, he may get 4 from the 1st grenade in the 1st box, and 1 from the 1st grenade in the 3rd box), while Bessie will obtain 10 from the remaining grenades.
After the second replacement, Angus will obtain 6 while Bessie will obtain 10. After the third replacement, Angus will obtain 6 while Bessie will obtain 9. In total, then, Angus will have obtained 5 + 6 + 6 = 17 grenade power, while Bessie will have obtained 10 + 10 + 9 = 29.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: May 07, 2017
Author: SourSpinach

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

Comments (Search)