問題一覧 > 通常問題

No.2961 Shiny Monster Master

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

ストーリー

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

11 周 2020 分くらいかかるんですよ...

問題文

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

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

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

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

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

    • 入力

    RR NN
A1A_1 ⋯\cdots ANA_N
QQ
l1l_1 r1r_1
…\ldots
lQl_Q rQr_Q

  • 2≤R≤1062 \leq R \leq 10^6
  • 1≤N≤min⁡(R,105)1 \leq N \leq \min(R,10^5)
  • 0≤Ai<R (1≤i≤N)0 \leq A_i < R\ (1 \leq i \leq N)
  • AiA_iはすべて異なる
  • 1≤Q≤20001 \leq Q \leq 2000
  • 1≤li<ri≤109 (1≤i≤Q)1 \leq l_i < r_i \leq 10^9 \ (1 \leq i \leq Q)
  • 入力はすべて整数

    • 出力

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

    サンプル

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

    22 つ目のクエリでは、1313 秒後のときカウンターが 33 となり、色違いが出現します。1616 秒後でカウンターが 11、1818 秒でカウンターが 33 となるので、全部で 33 回チャンスがあります。 　　　　　　

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

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