UT Invitational Programming Contest Fall 2019


2019-11-23 10:00 AKST

UT Invitational Programming Contest Fall 2019


2019-11-23 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -371 days 15:55:38

Time elapsed


Time remaining


Problem F
Dominant Conversations

Whenever people get together, there are some people who dominate regions of the conversation. We are given a record of a $N$-second long conversation which details who was talking at each second (people talk in second-long intervals). For each of $K$ people, your job is to find out the number of regions of the conversation they dominate. A region is a chunk of time from second $i$ to second $j$ inclusive, with $i \leq j$, and it is dominated by person $k$ if more that half of the entries in the range $[i,j]$ of the record are $k$.


The first line contains space-separated integers $n,k$ such that $1 \leq n,k \leq 10^6$. The second line contains $n$ space separated integers $a_ i$, the entries in the record. $0 \leq a_ i < k$


Output $k$ lines, the $i$th of which denotes the number of regions dominated by the $i$th person ($0$-indexed).

Sample Input 1 Sample Output 1
5 1
0 0 0 0 0
Sample Input 2 Sample Output 2
5 2
0 1 1 1 1