No.2338 Range AtCoder Query
タグ : / 解いたユーザー数 47
作問者 : SSRS / テスター : Forested 👑 Nachia
問題文
長さ $N$ の数列 $P_1, P_2, \dots, P_N$ と $N$ 個の文字列 $S_1, S_2, \dots, S_N$ が与えられます。ただし、$S_i$ ($1 \leq i \leq N)$ は AC
または WA
です。
$Q$ 個のクエリが与えられるので、処理してください。
$i$ 番目 ($1 \leq i \leq Q$) のクエリでは整数 $L_i, R_i$ が与えられるので、以下の問題を解いてください。高橋くんは $M$ 問の問題からなるプログラミングコンテストに参加し、コンテスト中に $R_i-L_i+1$ 回の提出を行いました。
$j$ 回目 ($1 \leq j \leq R_i-L_i+1$) の提出は $P_{L_i+j-1}$ 番目の問題への提出であり、結果は $S_{L_i+j-1}$ です。
高橋くんの正答数は、
AC
を $1$ 回以上出した問題の個数です。高橋くんのペナルティ数は、
AC
を $1$ 回以上出した各問題に対する、最初のAC
提出の前のWA
提出の個数の総和です。高橋くんの正答数とペナルティ数を求めてください。
入力
入力は以下の形式で標準入力から与えられます。
$N$ $M$ $Q$ $P_1$ $S_1$ $P_2$ $S_2$ $\vdots$ $P_N$ $S_N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$
出力
標準出力に $Q$ 行出力してください。$i$ 行目 ($1 \leq i \leq Q$) には、クエリ $i$ での高橋くんの正答数とペナルティ数をこの順に空白区切りで出力してください。
最後に改行してください。
制約
入力は以下の制約を満たします。
- $1 \leq N \leq 200\,000$
- $1 \leq M \leq 200\,000$
- $1 \leq Q \leq 200\,000$
- $1 \leq P_i \leq M$ ($1 \leq i \leq N)$
- $S_i$ ($1 \leq i \leq N$) は
AC
またはWA
である。 - $1 \leq L_i \leq R_i \leq N$ ($1 \leq i \leq Q)$
- $N,M,Q,P_i,L_i,R_i$ はすべて整数である。
サンプル
サンプル1
入力
5 5 5 3 WA 3 AC 2 AC 5 WA 2 WA 1 2 3 3 2 4 2 5 1 5
出力
1 1 1 0 2 0 2 0 2 1
クエリ $1$ では、高橋君が AC
を $1$ 回以上出したのは $3$ 番目の問題のみなので、正答数は $1$ です。また、$3$ 番目の問題で AC
を最初に出すまでに WA
を $1$ 回出しているので、ペナルティ数は $1$ です。
クエリ $2$ では、高橋君が AC
を $1$ 回以上出したのは $2$ 番目の問題のみなので、正答数は $1$ です。また、$2$ 番目の問題で AC
を最初に出すまでに WA
を出していないので、ペナルティ数は $0$ です。
クエリ $3$ では、高橋君が AC
を $1$ 回以上出したのは $2$ 番目・$3$ 番目の問題なので、正答数は $2$ です。また、$2$ 番目・$3$ 番目の問題で AC
を最初に出すまでに WA
を出していないので、ペナルティ数は $0$ です。
クエリ $4$ では、高橋君が AC
を $1$ 回以上出したのは $2$ 番目・$3$ 番目の問題なので、正答数は $2$ です。また、$2$ 番目・$3$ 番目の問題で AC
を最初に出すまでに WA
を出していないので、ペナルティ数は $0$ です。
クエリ $5$ では、高橋君が AC
を $1$ 回以上出したのは $2$ 番目・$3$ 番目の問題なので、正答数は $2$ です。また、$2$ 番目・$3$ 番目の問題で AC
を最初に出すまでに WA
をそれぞれ $0,1$ 回出しているので、ペナルティ数は $1$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。