IPSC 2016 Problem J – Jumping queues

IPSC 2016

Problem J – Jumping queues

You probably know this situation really well. You’re in a supermarket, standing in a long queue in front of a cashier. Around you, there are several other long queues and it always seems like they’re moving much faster than yours. Sure, you can always leave the current queue and move to the end of another one – but after you do so, it still seems like the other queues are moving much faster than your new one. The queues are moving towards the cashiers, but they also grow in time. Still, the longer a queue already is, the slower it tends to grow.

Sometimes, you note that something changed. It may be the speed at which the queues are moving. It may be the rate at which the queues are growing. It may be that a new cashier has just been opened and a queue of a given length has instantly spawned in front of that cashier. (As you can see, this is a very realistic model.)

In order to determine whether jumping queues is worth the effort, you’d like to know the answers to several questions of the following form: “Suppose a person just arrived to the checkouts. They are going to choose a queue and wait in that queue until they reach its cashier. Assuming that the queues will maintain their current speeds, what is the shortest time in which the person can reach one of the cashiers?”

Problem specification

There are n points of sale (POS) numbered 1 through n. Each of them is either open or closed. Initially, POS numbered 1 through m are open. If the POS number i is open, there’s a cashier at that POS and a queue in front of the POS. The speed of the queue at POS i is v_i. (More precisely, v_i is the speed at which you’re moving towards the cashier if you’re standing in that queue.) This queue also has a growth parameter g_i. The length l_i of the i-th queue is a function of the time c: if the POS number i is open, the length l_i(c) grows continuously. The rate of growth is given by the following formula:

$$ \frac{\mathrm{d} l_i}{\mathrm{d}c}=\frac{g_i}{l_i}\,. $$

Let τ_i(c) be the time necessary to reach the cashier when you’re standing at the end of queue i at time c, provided that the speed v_i of this queue will remain constant.

You should process q queries of three types:

“O c i v g l”: POS number i has opened at time c; there is a new queue of length l_i(c)=l with parameters v_i = v, g_i = g in front of it
“U c i v g”: at time c, the parameters of queue i change to v and g
“Q c”: find an open queue i for which τ_i(c) (the waiting time if you joined it at time c) is shortest, and answer that waiting time

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

The first line of each test case contains three space-separated integers n, m and q. Each of the following m lines contains three space-separated real numbers v, g and l: the speed, the growth parameter, and the length of queue i at time c = 0. Then, q lines follow; each of them contains the description of one query in the format above; c, v, g and l are real numbers given with exactly two digits after the decimal point.

In both subproblems, 1 ≤ m ≤ n ≤ 2 000 000, 1 ≤ q ≤ 5 000 000, 1 ≤ c, v, g, l ≤ 10 000 000. In addition, the time c in successive queries (even queries of different types) will be increasing; in type U queries, the speed of each queue will be non-decreasing and the growth parameter non-increasing.

In the easy subproblem J1, there will be no queries of types O and U.

It’s guaranteed that the number of queries of type Q in each test case will be a multiple of 5 000.

This problem has large input files. You cannot download them directly. Instead, we have provided small Python 2 programs j1gen.py and j2gen.py that will generate j1.in and j2.in when executed. Each generator should take under 10 minutes to run on average hardware. We recommend running them early – for example, starting them as you start working on your solution for this problem.

Output specification

For each test case, let q′ be the number of queries of type Q. Print q′/5000 numbers on separate lines: the sum of the first five thousand answers, then the sum of the next five thousand answers, etc. Answers with absolute or relative error up to 10⁻⁶ will be accepted.

Example

Input:

2

5 2 3
1.00 3.00 50.00
2.00 14.00 15.00
Q 100.00
Q 2000.00
Q 4000.00

5 1 4
8.00 8.00 8.00
O 1.50 4 2.70 3.00 5.44
Q 2.55
U 7.20 1 27.00 2.61
Q 10.00

Output:

308.8472630
1.7952699

In the above examples the number of queries of type Q is not a multiple of 5000. The first number in the example output is the sum of all three answers to the queries in the first example test case, the second number is the sum of both answers in the second example test case.

The answers to the five individual type-Q queries in the example are 27.5000000 + 118.5590570 + 162.7882060 in the first test case and 1.2796484 + 0.5156215 in the second test case.