問題一覧 > 通常問題

No.2961 Shiny Monster Master

レベル : / 実行時間制限 : 1ケース 1.777秒 / メモリ制限 : 477 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 60
作問者 : ねしんねしん / テスター : 👑 p-adicp-adic
1 ProblemId : 11079 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-16 18:26:12

ストーリー

色違い絶賛沼っている最中です。助けてください。

$1$ 周 $20$ 分くらいかかるんですよ...

問題文

大人気モンスターのゲームが発売されました。そのゲームではまれに色違いと呼ばれる珍しいモンスターが出現します。

このゲームでは $R$ 秒周期のカウンターが使われています。ゲームを起動した時点ではカウンターの値は $0$ であり、起動した直後から $1$ 秒ごとに $1$ ずつ増えていきます。ただし、カウンターの値が $R-1$ までくると $0$ に戻ります。

また、色違いはカウンターが $A_i(1 \leq i \leq N)$ の時に必ず出現し、それ以外では出現しないことがわかっています。

ここで、今から $Q$ 個のクエリが渡されます。$i$ 番目 $(1 \leq i \leq Q)$ のクエリでは $l_i,r_i$ が与えられます。以下の問いに答えてください。

  • ゲームを起動して $l_i$ 秒後から $r_i$ 秒後までの間に色違いを捕まえるチャンスの数を答えてください。ここで答えるべきチャンスの数とは、$l_i \leq t \leq r_i$ を満たし、「ゲームを起動してから $t$ 秒後に色違いが出る。」が真となる整数 $t$ の個数です。

    • 入力

    $R$ $N$
$A_1$ $\cdots$ $A_N$
$Q$
$l_1$ $r_1$
$\ldots$
$l_Q$ $r_Q$

  • $2 \leq R \leq 10^6$
  • $1 \leq N \leq \min(R,10^5)$
  • $0 \leq A_i < R\ (1 \leq i \leq N)$
  • $A_i$はすべて異なる
  • $1 \leq Q \leq 2000$
  • $1 \leq l_i < r_i \leq 10^9 \ (1 \leq i \leq Q)$
  • 入力はすべて整数

    • 出力

    $Q$ 行出力してください。$i(1\leq i \leq Q)$ 行目には $i$ 番目のクエリの答えを出力してください。

    サンプル

    サンプル1
    入力
    5 2
1 3
3
1 4
13 20
89 90
    出力
    2
3
0

    $2$ つ目のクエリでは、$13$ 秒後のときカウンターが $3$ となり、色違いが出現します。$16$ 秒後でカウンターが $1$、$18$ 秒でカウンターが $3$ となるので、全部で $3$ 回チャンスがあります。 　　　　　　

    なお、ゲームを起動してから $l_i$ 秒後、$r_i$ 秒後に出現する色違いも含みますので注意してください。

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