[Solution] Fishingprince Plays With Array Again Codeforces Solution

[Solution] Fishingprince Plays With Array Again Codeforces Solution

G. Fishingprince Plays With Array Again

time limit per test

6 seconds

memory limit per test

1024 megabytes

input

standard input

output

standard output

Suppose you are given a 1-indexed sequence a$a$ of non-negative integers, whose length is n$n$, and two integers x$x$, y$y$. In consecutive t$t$ seconds (t$t$ can be any positive real number), you can do one of the following operations:

• Select 1≤i<n$1\le i<n$, decrease ai$a_i$ by x⋅t$x\cdot t$, and decrease ai+1$a_{i+1}$ by y⋅t$y\cdot t$.
• Select 1≤i<n$1\le i<n$, decrease ai$a_i$ by y⋅t$y\cdot t$, and decrease ai+1$a_{i+1}$ by x⋅t$x\cdot t$.

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$0$ as f(a)$f(a)$.

For example, when x=1$x=1$, y=2$y=2$, it takes 3$3$ seconds to deal with the array [3,1,1,3]$[3,1,1,3]$. We can:

• In the first 1.5$1.5$ seconds do the second operation with i=1$i=1$.
• In the next 1.5$1.5$ seconds do the first operation with i=3$i=3$.

We can prove that it's not possible to make all elements less than or equal to 0$0$ in less than 3$3$ seconds, so f([3,1,1,3])=3$f([3,1,1,3])=3$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Now you are given a 1-indexed sequence b$b$ of positive integers, whose length is n$n$. You are also given positive integers x$x$, y$y$. Process q$q$ queries of the following two types:

• 1 k v: change bk$b_k$ to v$v$.
• 2 l r: print f([bl,bl+1,…,br])$f([b_l,b_{l+1},\dots ,b_r])$.

Input

NIT orz! Codeforces Solution

NIT Destroys the Universe Codeforces Solution 

Fishingprince Plays With Array Codeforces Solution

Permutation Graph Codeforces Solution

Placing Jinas Codeforces Solution 

Tree Recovery Codeforces Solution

Fishingprince Plays With Array Again Codeforces Solution

Maximum Product? Codeforces Solution

The first line of input contains two integers n$n$ and q$q$ (2≤n≤2⋅105$2\le n\le 2\cdot {10}^5$, 1≤q≤2⋅105$1\le q\le 2\cdot {10}^5$).

The second line of input contains two integers x$x$ and y$y$ (1≤x,y≤106$1\le x,y\le {10}^6$).

The third line of input contains n$n$ integers b1,b2,…,bn$b_1,b_2,\dots ,b_n$ (1≤bi≤106$1\le b_i\le {10}^6$).

This is followed by q$q$ lines. Each of these q$q$ lines contains three integers. The first integer op$op$ is either 1$1$ or 2$2$.

• If it is 1$1$, it is followed by two integers k$k$, v$v$ (1≤k≤n$1\le k\le n$, 1≤v≤106$1\le v\le {10}^6$). It means that you should change bk$b_k$ to v$v$.
• If it is 2$2$, it is followed by two integers l$l$, r$r$ (1≤l<r≤n$1\le l<r\le n$). It means that you should print f([bl,bl+1,…,br])$f([b_l,b_{l+1},\dots ,b_r])$.

Output

For each query of type 2$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${10}^{-9}$.