問題一覧 > 通常問題

No.2698 Many Asakatsu

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : karinohitokarinohito / テスター : KowerKoint2010KowerKoint2010 timitimi hibit_athibit_at
3 ProblemId : 10767 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-23 03:08:02

問題文

Discord サーバー「あさかつ」では、多様な需要に合わせて難易度の異なる $N$ 個のバーチャルコンテストを開催しています。
各コンテストは $M$ 問からなり、$i$ 個目のコンテストの $j$ 問目の難易度は $D_{i,j}$ です。
ここで、$D_{i,j}$ について以下が成り立つことが保証されます。

  • $D_{i,j}\le D_{i,j+1}$ $(1\le i\le N,\ 1\le j\lt M)$
  • $D_{i,j}\le D_{i+1,j}$ $(1\le i\lt N,\ 1\le j\le M)$
  • 各 $i$ $(1\le i\le N)$ について、$D_{i,1},D_{i,2},\dots,D_{i,M}$ はこの順に等差数列をなす

ただし、入力では $D_{i}$ の初項 $A_i$ と公差 $B_i$ のみが与えられ、$D_{i,j}$ の値は陽に与えられません。

hibit 君はこれらのコンテストに延べ $Q$ 回参加することにしました。
hibit 君の $1$ 回目のコンテスト参加前のレートは $X$ であり、$i$ 番目のコンテストに参加をする度にレートが $C_i$ 増加します。

hibit 君は各回に参加する前の時点でのレートと問題の難易度の差の総和が最も小さいコンテストに参加します。
より具体的には、$q$ 回目の参加前の hibit 君のレートを $R$ とし、$d(i)=\sum_{j=1}^{M}|D_{i,j}-R|$ としたときの $d(i)$ の最小値を $m$ として、$d(i)=m$ なる $i$ が hibit 君が $q$ 回目に参加するコンテストの番号です。
ただし、$d(i)=m$ なる $i$ が複数ある場合、その中での最小値を参加するコンテストの番号とします。

$q=1,2,\dots,Q$ に対し、hibit 君が $q$ 回目に参加するコンテストの番号を出力してください。

入力

$N$ $M$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
$\vdots$
$A_{N}$ $B_{N}$ 
$Q$ $X$
$C_1$ $C_2$ $\dots$ $C_N$

  • 入力はすべて整数
  • $2 \leq N\leq 10^5$
  • $2 \leq M\leq 10^9$
  • $1 \leq Q \leq 2\times 10^5$
  • $0 \leq X \leq 10^9$
  • $D_{i,j}=A_{i}+(j-1)B_{i}$ とした時以下が成立
    • $0 \leq D_{i,j} \leq 10^9$ $(1\le i\le N,1\le j\le M)$
    • $D_{i,j}\le D_{i,j+1}$ $(1\le i\le N,\ 1\le j\lt M)$
    • $D_{i,j}\le D_{i+1,j}$ $(1\le i\lt N,\ 1\le j\le M)$
  • $0 \leq C_i \leq 10^9$ $(1\le i\le N)$

出力

$q=1,2,\dots,Q$ に対して、答えを空白区切りで出力せよ。

サンプル

サンプル1
入力
3 3
1 2
6 0
7 1
2 4
3 1 4
出力
1 2

各コンテストの各問題の難易度は以下の通りです。

$1$ 問目 $2$ 問目 $3$ 問目
$1$ 番目のコンテスト $1$ $3$ $5$
$2$ 番目のコンテスト $6$ $6$ $6$
$3$ 番目のコンテスト $7$ $8$ $9$
$1$ 回目の参加について、$1$ 番目のコンテストの難易度とレートの差の総和は $|1-4|+|3-4|+|5-4|=5$ です。同様に、$2,3$ 番目のコンテストの難易度とレートの差の総和は、$6$, $12$ です。最小は $1$ 番目の $5$ なので、$1$ 番目に参加します。
$1$ 回目の参加後、hibit君のレートは $4+C_{1}=4+3=7$ となります。
$2$ 回目の参加について、$1,2,3$ 番目のコンテストの難易度とレートの差の総和はそれぞれ、$12,3,3$ です。最小は $2,3$ 番目の $3$ なので、このうち番号の小さな $2$ 番目に参加します。
サンプル2
入力
6 4
0 5
0 6
1 7
6 6
6 10
9 9
5 11
1 12 13 11 25 14
出力
1 1 4 4 6
同じコンテストに複数回参加する場合もあり、その場合でもその都度レートは増加します。
サンプル3
入力
4 4
0 0
1 1
3 3
5 5
4 4229
1 10 100 1000
出力
4 4 4 4

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