Codeforces Global Round 21 |
---|
Finished |
Suppose you are given a 1-indexed sequence $$$a$$$ of non-negative integers, whose length is $$$n$$$, and two integers $$$x$$$, $$$y$$$. In consecutive $$$t$$$ seconds ($$$t$$$ can be any positive real number), you can do one of the following operations:
Define the minimum amount of time (it might be a real number) required to make all elements in the sequence less than or equal to $$$0$$$ as $$$f(a)$$$.
For example, when $$$x=1$$$, $$$y=2$$$, it takes $$$3$$$ seconds to deal with the array $$$[3,1,1,3]$$$. We can:
We can prove that it's not possible to make all elements less than or equal to $$$0$$$ in less than $$$3$$$ seconds, so $$$f([3,1,1,3])=3$$$.
Now you are given a 1-indexed sequence $$$b$$$ of positive integers, whose length is $$$n$$$. You are also given positive integers $$$x$$$, $$$y$$$. Process $$$q$$$ queries of the following two types:
The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$1\le q\le 2\cdot 10^5$$$).
The second line of input contains two integers $$$x$$$ and $$$y$$$ ($$$1\le x,y\le 10^6$$$).
The third line of input contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$1\le b_i\le 10^6$$$).
This is followed by $$$q$$$ lines. Each of these $$$q$$$ lines contains three integers. The first integer $$$op$$$ is either $$$1$$$ or $$$2$$$.
For each query of type $$$2$$$, print one real number — the answer to the query. Your answer is considered correct if its absolute error or relative error does not exceed $$$10^{-9}$$$.
4 3 1 2 3 1 1 4 2 1 4 1 1 1 2 1 3
3.500000000000000 1.000000000000000
Let's analyse the sample.
In the first query, we are asked to compute $$$f([3,1,1,4])$$$. The answer is $$$3.5$$$. One optimal sequence of operations is:
In the third query, we are asked to compute $$$f([1,1,1])$$$. The answer is $$$1$$$. One optimal sequence of operations is:
Name |
---|