GlobeX Cup '19 S1 - Planet Classification

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

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

Andy is travelling through the galaxy. His mission is to categorize the planets that he passes. There are K types of planets. He passes by N different planets. Each of these planets can be classified as one of these K types. You would like to help Andy on his mission by programming a computer assistant for him. Whenever he passes a planet, he will tell the assistant the type of this planet. The assistant must then tell him how many previous planets are of this type. At the end of his journey, the assistant must also report the total different types of planets that he has passed by.

Input Specification

Line 1: N and K, separated by a single space.

Line 2 to N + 1: a_i, the type of the planet that he has passed, where i + 1 is the line number.

Output Specification

Line 1 to N: b_i, the number of previous planets that are of type a_i, where i is the line number.

Line N + 1: t, the total number of different types of planets that Andy has passed.

Constraints

1 \leq N \leq 10^5

1 \leq K \leq 10^9

1 \leq a_i \leq K

Subtasks

Subtask 1 [10%]

N \leq 1000

Subtask 2 [10%]

K \leq 10^6

Subtask 3 [80%]

No additional constraints.

Sample Input

5 4
1
4
4
3
4

Sample Output

0
0
1
0
2
3

Comments

There are no comments at the moment.