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

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 1.8s
Java 3.0s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 more ice cream cones, each at P dollars.

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

BUYAMT Q - Nick has 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 cheapest cones Richard is selling, or all of them if Richard is selling fewer than L of them. Report the total cost of the cones bought.

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

COST L - Report the cost of the Lth cheapest cone. If there are fewer than 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.

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 contains a single positive integer N, the number of operations to support. N will be at most 3 \cdot 10^5.

Each of the next 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 < A \le B \le 2 \cdot 10^6, 0 < L \le 10^{12}, and 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

2
7
13
4
6
25

Comments


  • 3
    insect  commented on Feb. 10, 2018, 3: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


    • 4
      echofox  commented on April 24, 2018, 6:32 a.m.

      nice.


  • 1
    insect  commented on Feb. 9, 2018, 9:44 a.m.

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