Editorial for WC '18 Contest 1 S4 - Bad Influence

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.

Let $V_i$ $V_{i}$ be the volatility of students $1 \dots i$ $1 \dots i$ . The volatility of a set of students is simply the number of students $i$ $i$ who cannot be coerced into using their phones by anybody else (in other words, the number of students $i$ $i$ for which there exists no student $j$ $j$ such $S_i < S_j$ $S_{i} < S_{j}$ and $D_j-R_j \le D_i \le D_j+R_j$ $D_{j} - R_{j} \leq D_{i} \leq D_{j} + R_{j}$ ). We can thus think of each student as contributing either $0$ $0$ or $1$ $1$ volatility to each $V$ $V$ value. Let $M_i$ $M_{i}$ be the smallest value of $j$ $j$ which satisfies the above conditions (or $M_i = N+1$ $M_{i} = N + 1$ if there's no such $j$ $j$ ). If $M_i \le i$ $M_{i} \leq i$ , then student $i$ $i$ contributes no volatility at all, and otherwise, they contribute $1$ $1$ volatility to each of the values $V_{i \dots (M_i-1)}$ $V_{i \dots (M_{i} - 1)}$ . So, if we had the values $M_{1 \dots N}$ $M_{1 \dots N}$ , we could use them to compute the volatilities $V_{1 \dots N}$ $V_{1 \dots N}$ with a simple $\mathcal O(N)$ $O (N)$ sweep.

What remains is computing the values $M_{1 \dots N}$ $M_{1 \dots N}$ efficiently. Let's process the $N$ $N$ students in decreasing order of $S$ $S$ value, either by explicitly sorting them by their $S$ $S$ values, or by keying them by their $S$ $S$ values and then iterating over all possible $S$ $S$ values from $10^6$ $10^{6}$ down to $1$ $1$ . Let $X_d$ $X_{d}$ be the minimum index (in the original ordered student list) of any student processed so far whose range of influence includes desk $d$ $d$ (or $X_d = \infty$ $X_{d} = \infty$ if there's been no such student so far). When processing student $i$ $i$ , we can observe that $M_i$ $M_{i}$ must be equal to $X_{Pi}$ $X_{P i}$ . And upon finishing with student $i$ $i$ , we should update $X_d$ $X_{d}$ to $\min(X_d, i)$ $min (X_{d}, i)$ for each desk $d$ $d$ in the inclusive interval $[D_i-R_i, D_i+R_i]$ $[D_{i} - R_{i}, D_{i} + R_{i}]$ .

Let's maintain the values $X_{1 \dots K}$ $X_{1 \dots K}$ (where $K$ $K$ is the maximum possible $D$ $D$ value) using a segment tree with lazy propagation, in which each node stores the minimum value of any $X$ $X$ value in its interval, as well as the minimum new value which all $X$ $X$ values in its interval should lazily be updated with. This allows us to both query an $X$ $X$ value and update a range of $X$ $X$ values as necessary in $\mathcal O(\log K)$ $O (\log K)$ time each, resulting in an overall time complexity of $\mathcal O((N \log K)+Z)$ $O ((N \log K) + Z)$ (where $K$ $K$ is the maximum possible $D$ $D$ value and $Z$ $Z$ is the maximum possible $S$ $S$ value).

Comments

There are no comments at the moment.