DMOPC '19 Contest 3 P5 - Festival

View as PDF

Submit solution

Points: 20
Time limit: 2.5s
Memory limit: 256M

Author:
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

To prepare for his village's annual festival, Rexzae plans on putting on a display of fireworks. According to the village's spiritual beliefs, each firework is associated with a particular number, which they call its "colour". Currently, he has already set up N of these fireworks, the ith of which has "colour" c_i. In the following Q minutes, one of three events may occur. On the jth minute, Rexzae may add a new firework that has colour d_j, he may decide to adjust all of the fireworks he currently has set up by adding a_j to all of their colours, or he might want to know the minimum cost for setting up a fireworks display that has a festivity of k_j. The cost for this fireworks display is the minimum number of moves that it will take for Rexzae to make all of his fireworks have a colour that is a multiple of k_j. (Here, a move is defined as adding or subtracting 1 from the colour of a single firework.) Since Rexzae is greedy, each subsequent query of the third type must have a strictly larger value of k_j then the ones that came before.

Constraints

In all subtasks,
1 \le N,Q \le 300\,000
-10^6 \le a_j \le 10^6
-10^{12} \le c_i,d_j\le 10^{12}
1 \le k_j \le 10^{12}
The range of the colours of the different fireworks will not exceed 200\,000 at any time.

Subtask 1 [20%]

1\le N,Q \le 2000

Subtask 2 [30%]

There are no queries of the first or second type.

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, N and Q.
The second line contains N space-separated integers, c_1,c_2,\ldots,c_N.
Q lines will follow, each of which will be in the form of one of the following:

1 d - Rexzae adds a new firework with colour d.
2 a - Rexzae adds a to the colour of all of his fireworks.
3 k - Rexzae wants to know the minimum cost for setting up a fireworks display that has a festivity of k.

Note: Rexzae does not actually change the colours of his fireworks during a k operation.

Output Specification

For each query of the third type, output the minimum cost for setting up a fireworks display that has a festivity of k_j.

Sample Input

5 9
1 3 5 7 9
3 1
3 2
2 -3
3 3
1 14
2 5
3 5
3 7
3 10

Sample Output

0
5
3
7
12
14

Comments

There are no comments at the moment.