Editorial for QCC P6 - Freedom! - Olympiads Online Judge

Editorial for QCC P6 - Freedom!

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: qwertytown4life

Subtask 1

For each query, sum the cost from each house to $h_i$ $h_{i}$ via simulation.

Time Complexity: $\mathcal{O}(QN^2)$ $O (Q N^{2})$

Subtask 2

For each query, use a pointer on the left and right side of $h_i$ $h_{i}$ to simulate the cost.

Time Complexity: $\mathcal{O}(NQ)$ $O (N Q)$

Subtask 3

For the final subtask, there are a few different solutions. One solution involves building a prefix sum array and suffix sum array where:

$\text{psa}_i = \begin{cases} 0 & \text{if } i = 1 \\ \text{psa}_{i-1} + \text{abs}(a_i - a_{i-1}) \times (i-1) & \text{if } 1 < i \le N \end{cases}$ ${psa}_{i} = {\begin{cases} 0 & if i = 1 \\ {psa}_{i - 1} + abs (a_{i} - a_{i - 1}) \times (i - 1) & if 1 < i \leq N \end{cases}$

$\text{ssa}_i = \begin{cases} 0 & \text{if } i = N \\ \text{ssa}_{i+1} + \text{abs}(a_i - a_{i+1}) \times (N-i) & \text{if } 1 \le i < N \end{cases}$ ${ssa}_{i} = {\begin{cases} 0 & if i = N \\ {ssa}_{i + 1} + abs (a_{i} - a_{i + 1}) \times (N - i) & if 1 \leq i < N \end{cases}$

The answer for each query is $\text{psa}_{h_i} + \text{ssa}_{h_i}$ ${psa}_{h_{i}} + {ssa}_{h_{i}}$ . Note that the above solution uses $1$ $1$ -indexed arrays.

Time Complexity: $\mathcal{O}(N+Q)$ $O (N + Q)$

Comments

There are no comments at the moment.