DMOPC '19 Contest 7 P7 - Fluid Dynamics

View as PDF
Submit solution
Points: 35 (partial)
Time limit: 5.0s
Memory limit: 256M
Authors:
richardzhang, george_chen
Problem types

You have discovered a new type of fluid! You're extra excited because it comes in many different colours (which means more marketing potential, of course). It can be shown that these fluids can be mainly described by two characteristics: its volume and its colour. While messing around performing rigorous experiments, you have discovered that when you place two of these fluids together, one on top of the other, sometimes they will swap places! In particular, you discover that if you place a fluid of volume v_i and colour c_i on top of another fluid of volume v_j and colour c_j, the pair will have a potential, \phi, of (v_j \times c_j + (v_i+v_j) \times c_i). If the change in potential, \Delta \phi (defined as \phi_{new} - \phi_{old}), when the two fluids exchange places is greater than or equal to W (a value you've already determined), then the fluids will swap places. Otherwise, they will return to their original configuration (i.e. no swapping occurs).

As you are very interested in this process, you've decided to place a bunch of these fluids in a jar and see the result. Because of how the swapping process works, every time you place a new fluid into the jar, that fluid will keep exchanging places with the fluid directly below it in the jar, as long as it satisfies the swapping condition described above.

However, as doing this manually is incredibly laborious and you're very lazy busy, you've decided to create a program to simulate the results instead!

Input Specification

The first line will contain three integers, N, Q, and W.

The next N lines will contain two integers, v_i and c_i. Each pair corresponds to a fluid to insert. Place these fluids one by one in the given order at the top of the jar.

The next Q lines will each contain a query. There are two types of queries:

  • INSERT v c means to place a fluid of volume v and colour c at the top of the jar.
  • K-TH k means to output the k^\text{th} fluid's (counting from the bottom of the jar, starting from 1) characteristics (its volume and colour) separated by a single space.

Fluids do not combine! (Even if they are adjacent and have the same colour.)

Output Specification

For every query of type K-TH, output that fluid's volume and colour separated by a space on a new line.

Constraints

For all subtasks:

1 \le N,Q \le 200\,000

1 \le W \le 10^{14}

1 \le v_i, c_i \le 10^9

It is guaranteed that K-TH queries will refer to a valid index in the jar (i.e., greater than 1 and less than equal to the current number of fluids present in the jar).

Subtask 1 [10%]

1 \le N,Q \le 1\,000

Subtask 2 [90%]

No additional constraints.

Sample Input 1

5 5 7
15 2
20 12
7 16
7 12
20 3
K-TH 2
INSERT 1 10
INSERT 8 1
INSERT 9 1
K-TH 6

Sample Output 1

20 3
7 12

Explanation of Sample Output 1

For this sample input, W=7.

We start by placing the fluid (15,2) into the jar. Then we place fluid (20,12) into the jar. Before exchanging places, the potential of this pair is 450. After exchanging, the potential will be 310. Since \Delta \phi = 310-450=-140 < W, the two fluids will not swap places.

We then place the third fluid, (7,16) into the jar. The change in potential between (7,16) and (20,12) is \Delta \phi = -236 < W, so (7,16) and (20,12) will not swap places.

We then place the fourth fluid, (7,12) into the jar. The change in potential between (7,12) and (7,16) is \Delta \phi = 28 \ge W, so (7,12) and (7,16) will swap places. However, change in potential between (7,12) and the next fluid down, (20,12), is \Delta \phi = -156 < W, so (7,12) will not swap with (20,12).

Finally, for the fifth fluid, (20,3), this is the chain of events that will happen:

Fluid Directly Below \Delta \phi Will Swap Places?
(7,16) 299 Yes
(7,12) 219 Yes
(20,12) 180 Yes
(15,2) -5 No

Thus, for the first query, the second fluid from the bottom is (20,3). For the last query, the jar will look like:

1 10
7 16
7 12
20 12
9 1
8 1
20 3
15 2

So the fluid 6^\text{th} from the bottom would be (7,12).

Sample Input 2

10 10 25
41 12
35 7
18 49
25 47
19 47
28 25
4 6
8 29
30 24
35 26
INSERT 22 43
INSERT 2 19
INSERT 20 42
K-TH 7
K-TH 2
K-TH 10
K-TH 3
K-TH 11
INSERT 10 30
K-TH 8

Sample Output 2

25 47
41 12
19 47
35 26
18 49
22 43

Comments

There are no comments at the moment.