問題一覧 > 通常問題

No.3284 Picnic with Friends

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 30
作問者 : hirayuu_yc / テスター : highlighter
お気に入りにしたユーザー ProblemId : 12176 / 自分の提出
問題文最終更新日: 2025-09-26 19:47:22
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 484 (順位表) の他の問題:

Problem Statement

The Captain wants to go on a picnic with the Friends, because doing so yields a training item called the Small Sparkle Stone.

There are $N$ Friends. The Friends are numbered $1,2,\dots,N$, and the exploration ability of Friend $i$ is $S_i$.

The Captain intends to trigger $Q$ events. The $i$-th event is as follows.

  • $T_i$ hours from now, one of the following actions is performed, depending on whether a picnic is in progress.
    • If no picnic is in progress, start a picnic lasting $F_i+0.5$ hours.
    • If a picnic is in progress, extend the duration of the current picnic by $F_i$ hours.

In a continuous picnic lasting $x$ hours, Friend $i$ finds $\left\lfloor\frac{x}{S_i}\right\rfloor$ Small Sparkle Stones. Find the number of Small Sparkle Stones each Friend finds by the time all picnics have ended.

Constraints

  • $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$
  • All input values are integers.

Input

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

Output

Print $N$ lines. The $i$-th line should contain the number of Small Sparkle Stones found by Friend $i$.

Sample

Sample 1
Input
3
9 2 4
2
1 1
3 9
Output
1
4
2

A picnic of $1.5$ hours and a picnic of $9.5$ hours take place.

The number of Small Sparkle Stones obtained by each Friend is as follows.

  • Friend $1$: $\left\lfloor\frac{1.5}{9}\right\rfloor+\left\lfloor\frac{9.5}{9}\right\rfloor=0+1=1$
  • Friend $2$: $\left\lfloor\frac{1.5}{2}\right\rfloor+\left\lfloor\frac{9.5}{2}\right\rfloor=0+4=4$
  • Friend $3$: $\left\lfloor\frac{1.5}{4}\right\rfloor+\left\lfloor\frac{9.5}{4}\right\rfloor=0+2=2$
Sample 2
Input
3
9 2 4
2
1 1
2 9
Output
1
5
2

Only $T_2$ differs from Sample $1$. A picnic of $10.5$ hours now takes place, which changes the number of Small Sparkle Stones obtained by Friend $2$.

Sample 3
Input
5
1 9 9 2 4
5
1 1
2 9
14 9
20 2
26 4
Output
25
2
2
12
5

Picnics of $10.5,11.5,4.5$ hours take place.

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