No.3284 Picnic with Friends
タグ : / 解いたユーザー数 30
作問者 :
highlighter
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もしくは右上の雲マークをクリックしてアカウントを作成してください。