問題一覧 > 通常問題

No.1568 Sushi

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 6
作問者 : blackyukiblackyuki / テスター : KoDKoD PCTprobabilityPCTprobability
1 ProblemId : 6306 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-04-21 09:52:34

問題文

寿司取るな君は回転寿司店を営んでおり、寿司は環状のレーンによって客に届けられます。

レーンの長さは $L$ であり、$1$ 秒あたり長さ $1$ 動く速さで回っています。
初め、レーンは反時計回りに回っていますが、動く向きが反対になるタイミングが $N$ 回存在します。
$i \, (1 \leq i \leq N)$ 回目の切り替わりは時刻 $A_i$ に起こります。

また、レーンの周りには $L$ 個の椅子が等間隔に並んでおり、反時計回りに $0, 1, 2, \dots, L - 1$ と番号付けられています。

寿司取るな君は、客の注文に素早く対応するためのトレーニングとして、$Q$ 回からなる思考実験を行うことにしました。
$i \, (1 \leq i \leq Q)$ 回目の思考実験では、客が椅子 $x_i$ の前に、時刻 $t_i$ に訪れます。
寿司取るな君は、時刻 $t_i$ 以降(客が訪れた瞬間でも構いません)、注文された寿司を椅子 $0$ の前のレーン上に置くことができます。
客は、寿司が自分の目の前に来た瞬間に寿司を取ることができます。客が訪れた瞬間、あるいは寿司取るな君が寿司を置いた瞬間であってもよいです。
寿司取るな君は、彼が最適な時刻に寿司を置くとき、客が訪れてから寿司を取るまでの時間の最小値を求めたいです。

ただし、入力では直接的には $x_i, t_i$ の値は与えられません。これらの値を計算するための整数 $B_i, C_i$ が与えられるので、以下のように $x_i, t_i$ を定めてください。

  • $1$ 回目の思考実験の場合、$x_i = B_i, t_i = C_i$ とする。
  • $2$ 回目以降の思考実験の場合、$i-1$ 回目の思考実験の答えの値(問題の制約下で、これは整数であることが証明できる)を $D$ として、$x_i = (B_i + D) \bmod L, t_i = (C_i + D) \bmod 10^{15}$ とする。

  • (原案:harady)

    入力

    $L\, N\, Q$
    $A_1 \, A_2 \, A_3 \, \dots \, A_N$
    $B_1 \, C_1$
    $B_2 \, C_2$
    $\vdots$
    $B_Q \, C_Q$
    
  • 入力は全て整数
  • $1\leq L \leq 10^{15}$
  • $1\leq N \leq 2 \times 10^5$
  • $1\leq Q \leq 2 \times 10^5$
  • $1\leq A_i \leq 10^{15}\ ( 1\leq i \leq N)$
  • $A_i < A_{i+1} \, (1\leq i \leq N-1)$
  • $0 \leq B_i < L \, (1\leq i \leq Q)$
  • $0 \leq C_i < 10^{15} \, (1\leq i \leq Q)$
  • 出力

    合計 $Q$ 行出力してください。$i \,\, (1\leq i \leq Q)$ 行目には $i$ 回目の思考実験に対する答えを出力してください。 最後に改行してください。

    サンプル

    サンプル1
    入力
    10 3 3
    1 5 16
    8 0
    2 5
    3 9
    
    出力
    3
    5
    4
    

    まず、$1$ 回目の思考実験では $x=8,t=0$ です。このとき、時刻 $1$ に寿司を置くと時刻 $3$ に客に到着し、これが最適です。よって $3$ を出力してください。
    $2$ 回目の思考実験では $x=5,t=8$ です。このとき、時刻 $8$ に寿司を置くと時刻 $13$ に客に到着し、これが最適です。よって $5$ を出力してください。
    $3$ 回目の思考実験では $x=8,t=14$ です。このとき、時刻 $16$ に寿司を置くと時刻 $18$ に客に到着し、これが最適です。よって $4$ を出力してください。

    サンプル2
    入力
    20 2 1
    5 6
    7 0
    
    出力
    9
    

    時刻 $0$ に寿司を置くのが最適です。

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