Mock CCC '18 Contest 3 S5 - A Rage Tree Problem

Points: 20 (partial)

Time limit: 1.8s

Java 3.0s

Memory limit: 1G

Problem type

Richard has quit competitive programming and has opened an ice cream stand. Help him run his stand! Here are the operations to support:

ADD K P - Richard is now willing to sell $K$ ~K~ more ice cream cones, each at $P$ ~P~ dollars.

ADDRANGE A B - Richard is now willing to sell one more ice cream cone for each price $P$ ~P~ between $A$ ~A~ and $B$ ~B~, inclusive.

BUYAMT Q - Nick has $Q$ ~Q~ dollars, and buys the maximum number of cones he can, starting from cheapest to most expensive. Report how many cones Nick buys.

BUYLOW L - Nick buys the $L$ ~L~ cheapest cones Richard is selling, or all of them if Richard is selling fewer than $L$ ~L~ of them. Report the total cost of the cones bought.

BUYHIGH L - Nick buys the $L$ ~L~ most expensive cones Richard is selling, or all of them if Richard is selling fewer than $L$ ~L~ of them. Report the total cost of the cones bought.

COST L - Report the cost of the $L$ ~L~th cheapest cone. If there are fewer than $L$ ~L~ cones, return -1.

NUMCONES - Report how many cones Richard is currently selling.

TOTALCOST - Report the total cost of every cone that Richard is currently selling.

Constraints

For 2 marks, $N \le 100$ ~N \le 100~.

For 3 additional marks, there will be no BUYLOW, BUYHIGH, or COST operations.

For 4 additional marks, there will be no COST operations.

Input Specification

The first line will contain a single positive integer $N$ ~N~, the number of operations to support. $N$ ~N~ will be at most $3 \cdot 10^5$ ~3 \cdot 10^5~.

Each of the next $N$ ~N~ lines will contain information for one of the operations, as shown above.

As written above, $0 < K, P \le 2 \cdot 10^6$ ~0 < K, P \le 2 \cdot 10^6~, $0 < A \le B \le 2 \cdot 10^6$ ~0 < A \le B \le 2 \cdot 10^6~, $0 < L \le 10^{12}$ ~0 < L \le 10^{12}~, and $0 < Q \le 10^{18}$ ~0 < Q \le 10^{18}~.

Output Specification

For every operation that demands reporting a value, print out the desired value.

Sample Input

8
ADD 5 4
ADDRANGE 1 7
BUYAMT 3
BUYLOW 2
BUYHIGH 2
COST 1
NUMCONES
TOTALCOST

Sample Output

Comments

3

insect commented on Feb. 10, 2018, 8:26 p.m. ← edited →

Thanks to PlasmaVortex I now understand that the queries are also updates.

PS: Who the hell is stevenmai_uts and why do you have my name?

Edit: I also realized my comment below is number 6969

5

echofox commented on April 24, 2018, 10:32 a.m.

nice.

1

insect commented on Feb. 9, 2018, 2:44 p.m.

Is the test case correct? Shouldn't BUYLOW(2) = 3, COST(1) = 1, NUMCONES = 12, and TOTALCOST = 48?