codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1311C.md (3163B)


      1 Source: https://codeforces.com/problemset/problem/1311/C
      2 
      3 C. Perform the Combo
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You want to perform the combo on your opponent in one popular fighting game. The combo is the string $s$ consisting of $n$ lowercase Latin letters. To perform the combo, you have to press all buttons in the order they appear in $s$. I.e. if $s=$"abca" then you have to press 'a', then 'b', 'c' and 'a' again.
     22 
     23 You know that you will spend $m$ wrong tries to perform the combo and during the $i$-th try you will make a mistake right after $p_i$-th button ($1 \le p_i \lt n$) (i.e. you will press first $p_i$ buttons right and start performing the combo from the beginning). It is guaranteed that during the $m+1$-th try you press all buttons right and finally perform the combo.
     24 
     25 I.e. if $s=$"abca", $m=2$ and $p = [1, 3]$ then the sequence of pressed buttons will be 'a' (here you're making a mistake and start performing the combo from the beginning), 'a', 'b', 'c', (here you're making a mistake and start performing the combo from the beginning), 'a' (note that at this point you will not perform the combo because of the mistake), 'b', 'c', 'a'.
     26 
     27 Your task is to calculate for each button (letter) the number of times you'll press it.
     28 
     29 You have to answer $t$ independent test cases.
     30 
     31 Input
     32 
     33 The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     34 
     35 Then $t$ test cases follow.
     36 
     37 The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$) — the length of $s$ and the number of tries correspondingly.
     38 
     39 The second line of each test case contains the string $s$ consisting of $n$ lowercase Latin letters.
     40 
     41 The third line of each test case contains $m$ integers $p_1, p_2, \dots, p_m$ ($1 \le p_i \lt n$) — the number of characters pressed right during the $i$-th try.
     42 
     43 It is guaranteed that the sum of $n$ and the sum of $m$ both does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$, $\sum m \le 2 \cdot 10^5$).
     44 
     45 It is guaranteed that the answer for each letter does not exceed $2 \cdot 10^9$.
     46 
     47 Output
     48 
     49 For each test case, print the answer — $26$ integers: the number of times you press the button 'a', the number of times you press the button 'b', $\dots$, the number of times you press the button 'z'.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 3
     57 4 2
     58 abca
     59 1 3
     60 10 5
     61 codeforces
     62 2 8 3 2 9
     63 26 10
     64 qwertyuioplkjhgfdsazxcvbnm
     65 20 10 1 2 3 5 10 5 9 4
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 4 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
     72 0 0 9 4 5 3 0 0 0 0 0 0 0 0 9 0 0 3 1 0 0 0 0 0 0 0 
     73 2 1 1 2 9 2 2 2 5 2 2 2 1 1 5 4 11 8 2 7 5 1 10 1 5 2
     74 ```
     75 
     76 Note
     77 
     78 The first test case is described in the problem statement. Wrong tries are "a", "abc" and the final try is "abca". The number of times you press 'a' is $4$, 'b' is $2$ and 'c' is $2$.
     79 
     80 In the second test case, there are five wrong tries: "co", "codeforc", "cod", "co", "codeforce" and the final try is "codeforces". The number of times you press 'c' is $9$, 'd' is $4$, 'e' is $5$, 'f' is $3$, 'o' is $9$, 'r' is $3$ and 's' is $1$.