Problem Link: https://dmoj.ca/problem/ceoi22p5
Subtask 1
Define t_{i,j} = \frac12(D(j-i) - (a[j] - a[i])).
Notice that the answer will be \displaystyle\max_{i \leq j}t_{i,j}
Subtask 2
Let's binary search the answer.
Fix the answer as t.
Let b_1, b_2, ..., b_n as the final position of each person.
We calculate this answer as: b_1 = a_1 - t and b_i = \max(b_{i-1} + D, a_i - t)
To check if t is possible, check if adjacent positions are at least D units apart.
Subtask 3
Rearrange the formula from subtask 1.
t_{i,j} = \frac12((a[i] - Di) - (a[j] - Dj))Hence, it is enough to store a[i] - Di for each i.
Call this value val[i].
When person i is added, it is enough to find the maximum t_{i,j} over all j.
Subtask 4
Note that every time person i is added:
- val[j] for j < i does not change.
- val[j] for j > i is decreased by D.
- t_{j,k} for j, k < i or j, k > i does not change, and increased by D otherwise.
Observe that we need a data structure that supports range max/min query and range addition update.
Use segment tree to simulate this.