No.2404 Vertical Throw Up
タグ : / 解いたユーザー数 55
作問者 : 👑
amentorimaru
Problem Statement
Ruera conducted an experiment on the vertical upward throw motion of balls. In this experiment, she was supposed to add more balls to throw along the way and write in her experiment report, in order, the maximum displacement of the balls at specified times. However, since Ruera did not keep any experimental results, she decided to write the report based on predictions.
The gravitational acceleration on the planet where Ruera lives is given by $2a$. The displacement of a ball in vertical upward throw motion is expressed as a function of degree $2$ in time, and the coefficient of the degree $2$ term is $-a$. That is, the displacement $h$ of a ball at time $t$, during the period from when it is thrown up until it returns, can be expressed as $h=-at^2+bt+c$ using some constants $b,c$.
Answer the following $Q$ queries $\{q_i\}$.
1 s tAdd a ball to the experiment. The ball is thrown up from displacement $0$ at time $s$ and returns to displacement $0$ at time $t$.2 tPrint the maximum displacement of the balls at time $t$, followed by a newline. However, if no ball is in vertical upward throw motion at time $t$, print0followed by a newline.
It can be proved that, under the constraints of this problem, all values to be printed are integers.
In addition, the values $t$ given in queries of the form of query $2$ are non-decreasing in query order. That is, if $q_i\ (1\leq i\leq Q)$ is "$2\ t_i$" and $q_j\ (1\leq j\leq Q)$ is "$2\ t_j$", then $i\lt j$ implies $t_i\leq t_j$.
Input
$a$ $Q$ $q_1$ $q_2$ $q_3$ $\vdots$ $q_Q$
Each query $q_i\ (1\leq i\leq Q)$ is given in one of the following forms.
$1\ s\ t$
$2\ t$
- All input values are integers
- $1\leq a\leq 100$
- $2\leq Q\leq 10^5$
- $0\leq s\leq 10^8$
- $0\leq t\leq 10^8$
- For queries of the form
1 s t, $s\lt t$ - The values $t$ given in queries of the form
2 tare non-decreasing - Query $q_1$ is of the form
1 s t - There exists a query of the form
2 t
Output
For each query of the form 2 t, print the maximum displacement at time $t$ or $0$, followed by a newline.
Sample
Sample 1
Input
5 7 1 0 2 2 1 1 0 4 2 1 2 3 1 1 6 2 4
Output
5 15 15 30
Query $q_1$ adds a ball that is thrown up from displacement $0$ at time $0$ and returns to displacement $0$ at time $2$. The displacement $h_1$ of this ball at time $t$ can be expressed as $h_1=-5t^2+10t$. Substituting $t=1$ gives $h_1(1)=5$, so the output for query $q_2$ is 5.
Query $q_3$ adds a ball that is thrown up from displacement $0$ at time $0$ and returns to displacement $0$ at time $4$. The displacement $h_2$ of this ball at time $t$ can be expressed as $h_2=-5t^2+20t$. Substituting $t=1$ gives $h_1(1)=5,\ h_2(1)=15$, so the output for query $q_4$ is 15.
Sample 2
Input
5 3 1 0 2 1 4 6 2 3
Output
0
There may be no ball in vertical upward throw motion at the time $t$ given in a query of the form 2 t.
Sample 3
Input
3 10 1 2 4 2 1 2 3 2 4 1 0 5 2 4 2 6 1 1 9 2 6 2 8
Output
0 3 0 12 0 45 21
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。