Limits
1s, 512 MB

One day at group-”NDC TOP 100” of Notre Dame College, the ICT teacher gave the a students' a task by forming Q teams. He wrote N numbers in the board in a single line and called them array W. After that to each team, he gave five variables $(l, r, p, m, k)$.

Let, index $j$ be a point of division of the numbers from $l$ to $r$ i.e, $l \le j < r$

Let, $X = \frac{GXP([W_{l}...W_{j}], p)}{GXP([W_{j+1}...W_{r}], p)}$

Now he asked them if it was possible to find an index $j$ such that $X \ge m^k$. If there are multiple solutions then find an index $j$ such that it **minimizes** $X - m^k$

**Note:** The GXP function of any array $A$ with a given range $c$ to $d$ and parameter $p$ is the multiplication of the all the numbers in that range raised to the power $p$ i.e,

$GXP([A_{c}A_{c+1}…A_{d}], p) = A_{c}^{p} * A_{c+1}^{p} * ... * A_{d}^{p}$

Now there was a team which consist of two students naming Farhan Ishrak and Azmain Muksit. They were so called "Matbor" in their class. They wanted to solve all of the other teams' solutions along with their own to look cool. That being said, they collected every variable from the others. There was a problem though, they could not even solve their own. Thus they hired you to solve the problems on their behalf. Well, can you figure out the solution?

$1 < N \le 10^5$

$0 < Q, k, p \le 10^5$

$0 < W_i, m \le 10^9$

$0 < l < r \le N$

$N, Q$

$W_1\;W_2\;...\; W_N$

$l_1\; r_1\; p_1\; m_1\; k_1$

$l_2\; r_2\; p_2\; m_2\; k_2$

$.$

$.$

$l_Q\; r_Q\; p_Q\; m_Q\; k_Q$

For each team, if the answer is Yes, then print $YES$ followed by the valid index $j$ in a new line (see explanation of sample test case for better understanding), else print $NO$.

**Subtask 1 (for** $10$ **points):**

$1 < N \le 100$

$0 < Q \le 100$

$0 < W_i, p \le 10$

$0 < m^k \le 10^{18}$

**Subtask 2 (for** $30$ **points):** $1 < N \le 100$

**Subtask 3 (for** $60$ **points):** General Constraints

Input | Output |
---|---|

5 2 3 5 7 5 2 1 5 2 5 2 1 4 2 5 4 | YES 3 NO |

For the first team, when $j=3$, $X=\frac{GXP([3,5,7], 2)}{GXP([5,2], 2)}=\frac{3^2*5^2*7^2}{5^2*2^2}=110.25$ and $m^k=25$ which meets the given condition and $X-m^k$ is minimized

For the second team, the highest possible value of $X$ that can be found is $441$ which is less than $m^k=625$

Login to submit.

33%
Solution Ratio

user.828682Earliest,

user.828682Fastest, 0.3s

user.828682Lightest, 5.7 MB

user.828682Shortest, 658B

Toph uses cookies. By continuing you agree to our Cookie Policy.