問題一覧 > 通常問題

No.2338 Range AtCoder Query

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : SSRS / テスター : Forested 👑 Nachia
2 ProblemId : 5985 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-06-02 22:07:40

問題文

長さ NN の数列 P1,P2,…,PNP_1, P_2, \dots, P_N と NN 個の文字列 S1,S2,…,SNS_1, S_2, \dots, S_N が与えられます。ただし、SiS_i (1≤i≤N)1 \leq i \leq N) は AC または WA です。

QQ 個のクエリが与えられるので、処理してください。

ii 番目 (1≤i≤Q1 \leq i \leq Q) のクエリでは整数 Li,RiL_i, R_i が与えられるので、以下の問題を解いてください。

高橋くんは MM 問の問題からなるプログラミングコンテストに参加し、コンテスト中に Ri−Li+1R_i-L_i+1 回の提出を行いました。

jj 回目 (1≤j≤Ri−Li+11 \leq j \leq R_i-L_i+1) の提出は PLi+j−1P_{L_i+j-1} 番目の問題への提出であり、結果は SLi+j−1S_{L_i+j-1} です。

高橋くんの正答数は、AC を 11 回以上出した問題の個数です。

高橋くんのペナルティ数は、AC を 11 回以上出した各問題に対する、最初の AC 提出の前の WA 提出の個数の総和です。

高橋くんの正答数とペナルティ数を求めてください。

入力

入力は以下の形式で標準入力から与えられます。 

NN MM QQ
P1P_1 S1S_1
P2P_2 S2S_2
⋮\vdots
PNP_N SNS_N
L1L_1 R1R_1
L2L_2 R2R_2
⋮\vdots
LQL_Q RQR_Q

出力

標準出力に QQ 行出力してください。ii 行目 (1≤i≤Q1 \leq i \leq Q) には、クエリ ii での高橋くんの正答数とペナルティ数をこの順に空白区切りで出力してください。
最後に改行してください。

制約

入力は以下の制約を満たします。

  • 1≤N≤200 0001 \leq N \leq 200\,000
  • 1≤M≤200 0001 \leq M \leq 200\,000
  • 1≤Q≤200 0001 \leq Q \leq 200\,000
  • 1≤Pi≤M1 \leq P_i \leq M (1≤i≤N)1 \leq i \leq N)
  • SiS_i (1≤i≤N1 \leq i \leq N) は AC または WA である。
  • 1≤Li≤Ri≤N1 \leq L_i \leq R_i \leq N (1≤i≤Q)1 \leq i \leq Q)
  • N,M,Q,Pi,Li,RiN,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

クエリ 11 では、高橋君が AC を 11 回以上出したのは 33 番目の問題のみなので、正答数は 11 です。また、33 番目の問題で AC を最初に出すまでに WA を 11 回出しているので、ペナルティ数は 11 です。

クエリ 22 では、高橋君が AC を 11 回以上出したのは 22 番目の問題のみなので、正答数は 11 です。また、22 番目の問題で AC を最初に出すまでに WA を出していないので、ペナルティ数は 00 です。

クエリ 33 では、高橋君が AC を 11 回以上出したのは 22 番目・33 番目の問題なので、正答数は 22 です。また、22 番目・33 番目の問題で AC を最初に出すまでに WA を出していないので、ペナルティ数は 00 です。

クエリ 44 では、高橋君が AC を 11 回以上出したのは 22 番目・33 番目の問題なので、正答数は 22 です。また、22 番目・33 番目の問題で AC を最初に出すまでに WA を出していないので、ペナルティ数は 00 です。

クエリ 55 では、高橋君が AC を 11 回以上出したのは 22 番目・33 番目の問題なので、正答数は 22 です。また、22 番目・33 番目の問題で AC を最初に出すまでに WA をそれぞれ 0,10,1 回出しているので、ペナルティ数は 11 です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。