Reading KakaoTalk

For each person $p$, define

$$L_p=\max(\{i\mid A_i=p\}\cup\{0\}),$$

the index of the last message written by that person. The author condition is equivalent to $C_p\ge L_p$.

Set $B_0=N$ and $B_{M+1}=0$. Let be the number of people whose last read message is exactly . Then

$$D_k=B_k-B_{k+1}\qquad(0\le k\le M).$$

The input guarantees that $B$ is non-increasing, so every $D_k$ is a nonnegative integer.

Let $E_k$ be the number of people satisfying $L_p\le k$. Only these people may have $C_p=k$.

Choose the people with $C_p=k$ in increasing order of $k$. Before processing $k$, exactly

$$N-B_k$$

people have already received values smaller than $k$. Every such person satisfies $L_p\le k$. Therefore, the number of unassigned people who may receive value $k$ is

$$E_k-(N-B_k).$$

We must choose exactly $D_k$ of them. Hence the answer is

$$\prod_{k=0}^{M}\binom{E_k-(N-B_k)}{D_k}.$$

The problem guarantees that at least one valid sequence exists, so every selection step is feasible. An implementation may still check whether an upper argument is negative or smaller than $D_k$.

Compute every $L_p$, count their frequencies, and take prefix sums to obtain all $E_k$. With factorials and inverse factorials, each binomial coefficient is evaluated in constant time.

The time complexity is $O(N+M)$ and the memory complexity is $O(N+M)$.