25081번 - Cocktail Party 다국어

You are given a string of length $n$ representing the labels of $n$ cups of cocktail. The $i$-th cup of cocktail has label $s_i$, and the labels are among the 26 lowercase English letters. Let $\mathrm{Str}(l,r) = s_l s_{l+1} \cdots s_r$ be the string formed by the labels of the cocktails from the $l$-th cup to the $r$-th cup. If $\mathrm{Str}(p,p_0) = \mathrm{Str}(q,q_0)$ where $1 \le p \le p_0 \le n$, $1 \le q \le q_0 \le n$, $p \ne q$, $p_0-p+1 = q_0-q+1 = r$, we say the $p$-th cup of cocktail and $q$-th cup of cocktail are $r$-similar. Of course, for two cups of cocktail that are $r$-similar ($r > 1$) they are also 1-similar, 2-similar, ..., and $(r-1)$-similar. In particular, for any $1 \le p \le q \le n, p \ne q$, the $p$-th cup of cocktail and $q$-th cup of cocktail are $0$-similar.

Freda assigns the "deliciousness" for each cup of cocktail, and the $i$-th cup has deliciousness $a_i$. If we mix $p$-th cup of cocktail and $q$-th cup of cocktail, we may obtain cocktail with deliciousness $a_p a_q$. The problem asks for each $r = 0,\dots,n-1$, how many ways we may select two cups of cocktail that are $r$-similar, and compute the maximum possible deliciousness by mixing two cups of cocktail that are $r$-similar.

The first line of the input contains an integer $n$ denoting the number of cups of cocktail. The second line contains a string $S$ with length $n$ such that the $i$-th character denotes the label of the $i$-th cup of cocktail. The third line contains $n$ integers separated by a single space such that the $i$-th integer denotes the $i$-th cup of cocktail has deliciousness $a_i$.

The output contains $n$ lines. The $i$-th line contains two integers separated by a single space. The first integer denotes the number of ways to choose two cups of $(i-1)$-similar cocktails. The second integer denotes the maximum possible deliciousness by mixing two cups of cocktails that are $(i-1)$-similar. Notice if there does not exist two cups of cocktail that are $(i-1)$-similar, both integers in that line of the output shall be 0.

• $10 ≤ n ≤ 300\,000$
• $|a_i| \le 1\,000\,000\,000$