問題一覧 > 通常問題

No.3284 Picnic with Friends

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : hirayuu_yc / テスター : highlighter
ProblemId : 12176 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-09-26 19:47:22

問題文

隊長は、フレンズと一緒にピクニックをしたいです。小さな輝石と呼ばれる育成アイテムを手に入れられるためです。

$N$ 人のフレンズがいます。フレンズには $1,2,\dots,N$ と番号がついていて、フレンズ $i$ の探索能力は $S_i$ です。

隊長は、$Q$ 回のイベントを起こすつもりです。$i$ 番目のイベントは以下のようなものです。

  • 現在から $T_i$ 時間後に、ピクニックが行われているかにどうかよって以下のいずれか行動を行う。
    • ピクニックが行われていなければ、$F_i+0.5$ 時間のピクニックを始める。
    • ピクニックが行われていれば、今行われているピクニックの時間を $F_i$ 時間延長する。

フレンズ $i$ は、連続する $x$ 時間のピクニックで、小さな輝石を $\left\lfloor\frac{x}{S_i}\right\rfloor$ 個見つけます。すべてのピクニックが終わるまでに各フレンズが見つける小さな輝石の個数を求めてください。

制約

  • $1\leq N\leq 5\times 10^5$
  • $1\leq S_i\leq 10^{12}$
  • $1\leq Q\leq 10^5$
  • $1\leq T_i\leq 10^{12}$
  • $T_i\lt T_{i+1}$
  • $1\leq F_i\leq 10^5$
  • 入力はすべて整数

入力

$N$
$S_1$ $S_2$ $\dots$ $S_N$
$Q$
$T_1$ $F_1$
$T_2$ $F_2$
$\vdots$
$T_Q$ $F_Q$

出力

$N$ 行出力せよ。$i$ 行目には、フレンズ $i$ が見つける小さな輝石の個数を出力せよ。

サンプル

サンプル1
入力
3
9 2 4
2
1 1
3 9
出力
1
4
2

$1.5$ 時間のピクニックと $9.5$ 時間のピクニックがそれぞれ行われます。

各フレンズが獲得する小さな輝石の個数は以下のようになります。

  • フレンズ $1$：$\left\lfloor\frac{1.5}{9}\right\rfloor+\left\lfloor\frac{9.5}{9}\right\rfloor=0+1=1$
  • フレンズ $2$：$\left\lfloor\frac{1.5}{2}\right\rfloor+\left\lfloor\frac{9.5}{2}\right\rfloor=0+4=4$
  • フレンズ $3$：$\left\lfloor\frac{1.5}{4}\right\rfloor+\left\lfloor\frac{9.5}{4}\right\rfloor=0+2=2$
サンプル2
入力
3
9 2 4
2
1 1
2 9
出力
1
5
2

サンプル $1$ とは $T_2$ のみが異なります。$10.5$ 時間のピクニックが行われるようになり、フレンズ $2$ が獲得する小さな輝石の個数が変化しました。

サンプル3
入力
5
1 9 9 2 4
5
1 1
2 9
14 9
20 2
26 4
出力
25
2
2
12
5

$10.5,11.5,4.5$ 時間のピクニックがそれぞれ行われます。

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