問題一覧 > 通常問題

No.2961 Shiny Monster Master

レベル : / AI推定難易度 : 700 / 実行時間制限 : 1ケース 1.777秒 / メモリ制限 : 477 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 78
作問者 : twitteryou / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 11079 / 自分の提出
問題文最終更新日: 2024-11-16 18:26:12
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 453 (順位表) の他の問題:

Story

I'm currently stuck deep in the shiny-hunting swamp. Please help me.

One run takes about $20$ minutes per $1$ cycle...

Problem Statement

A hugely popular monster game has been released. In this game, rare monsters called shinies occasionally appear.

This game uses a counter with a period of $R$ seconds. When the game is started, the counter's value is $0$, and immediately after startup it increases by $1$ every $1$ second. However, once the counter's value reaches $R-1$, it returns to $0$.

It is also known that a shiny always appears when the counter is $A_i(1 \leq i \leq N)$, and does not appear otherwise.

You are now given $Q$ queries. In the $i$-th $(1 \leq i \leq Q)$ query, $l_i,r_i$ are given. Answer the following question.

  • Find the number of chances to catch a shiny between $l_i$ seconds and $r_i$ seconds after starting the game. Here, the number of chances to report is the number of integers $t$ that satisfy $l_i \leq t \leq r_i$ and for which the statement "a shiny appears $t$ seconds after starting the game" is true.

    • Input

    $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)$
  • All $A_i$ are distinct
  • $1 \leq Q \leq 2000$
  • $1 \leq l_i < r_i \leq 10^9 \ (1 \leq i \leq Q)$
  • All input values are integers

    • Output

    Output $Q$ lines. On the $i(1\leq i \leq Q)$-th line, output the answer to the $i$-th query.

    Sample

    Sample 1
    Input
    5 2
1 3
3
1 4
13 20
89 90
    Output
    2
3
0

    In the $2$nd query, at $13$ seconds the counter is $3$ and a shiny appears. At $16$ seconds the counter is $1$, and at $18$ seconds the counter is $3$, so there are $3$ chances in total. 　　　　　　

    Note that shinies appearing exactly $l_i$ seconds and $r_i$ seconds after starting the game are also included.

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