問題一覧 > 通常問題

No.2404 Vertical Throw Up

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 55
作問者 : 👑 獅子座じゃない人 / テスター : 👑 amentorimaru
お気に入りにしたユーザー ProblemId : 9819 / 自分の提出
問題文最終更新日: 2023-08-03 22:03:55
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 400 (順位表) の他の問題:

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 t Add 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 t Print 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$, print 0 followed 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 t are 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もしくは右上の雲マークをクリックしてアカウントを作成してください。