Analysis: Airplane Boarding by Steven Hao

We will compute the number of steps each cow takes before sitting down, starting with cow N and going down sequentially.

We will store a set of pairs of two integers. Each pair represents a seat and a time: a pair (3, 4) means that a cow wishing to move to seat infinity must pass by seat 3 at time 4.

For cow N, the set contains only (0, 0); the only restriction we have on cow N is that he must be at position 0 at time 0. For cow N - i, the set will contain at least (-i, 0) as cow N - i must be at position -i at time 0.

We can find the first time cow i can reach seat S[i] by searching the set for the pair (a, b) such that a < S[i] and b - a is maximized. If cow i is restricted by the pair (a, b), then cow i will reach seat S[i] at time b - a + S[i] and will sit down at time b - a + S[i] + T[i].

To maintain the set when transitioning from one cow to the next, we simply look at all the pairs the most recently inserted cow passed by and subtract 1 from the position. In other words: if cow i is in seat 5 at time 10, then cow i - 1 can not be past seat 4 at time 10.

This immediately yields a O(N^2) solution. We will store the set as an array of pairs.

For cow i, search for the pair (a, b) with the maximum value of b - a satisfying a < S[i]. Compute the time cow i sits down (V[i] = b - a + S[i] + T[i]). Then, insert the pair (S[i], V[i]) into the list (cow i must be at seat S[i] at time V[i]). To transition to cow i - 1, we perform a range update by replacing all (a, b) such that a <= S[i] with (a - 1, b). We then print out the maximum value of V taken over all cows.

The O(N log N) solution stores the set as a monotonic queue. We observe that we do not need to store two pairs (a, b) and (c, d) if a < c and b - a > d - c; the pair (c, d) will never be the maximum of any prefix. Furthermore, in any subset, the pair (a, b) with the maximum value of b - a is simply the pair with maximum a.

To maintain the monotonic queue, after inserting a pair (a, b), delete all pairs (c, d) with c >= a and d - c <= b - a. Note that the range update does not affect the order of the pairs within the monotonic queue.

We will need a data structure that can support the searching step, insertion step, and the range update step. A balanced binary search tree with lazy propagation can handle these each in O(log N) time, for a total runtime of O(N log N), which is fast enough for N = 200000. Below is my implementation using a skip-list, which is more or less equivalent to a BBST.

```
#include <cstdio>
#include <cstdlib>

const int MAXN = 200100;
const int MAXH = 22;

int S[MAXN];
int T[MAXN];

int nxt[MAXH + 1][MAXN];
int lazy[MAXH + 1][MAXN];

int A[MAXN];
int B[MAXN];

int N;
int cur = 0;

// all nodes between n and nxt[r][n], exclusive, must be decremented lazy[r][n]
times.
void down(int r, int n) {
if (r == 0) return;
bool first = true;
for(int x = n; x != nxt[r][n]; x = nxt[r - 1][x]) {
if (!first) A[x] -= lazy[r][n];
first = false;
lazy[r - 1][x] += lazy[r][n];
}
lazy[r][n] = 0;
}

// a node in level i of skiplist has probability p = 0.5 of appearing in level
i + 1
int geth() {
for(int i = 0; i < MAXH; ++i) {
if (rand() % 2) return i;
}
return MAXH; // return MAXH if height > MAXH
}

// compares by B - A.
bool better(int x, int y) {
return B[x] - A[x] >= B[y] - A[y];
}
// sidenote: could make code cleaner by storing B - A in array instead of B

int main() {
if (fopen("boarding.in", "r")) {
freopen("boarding.in", "r", stdin);
freopen("boarding.out", "w", stdout);
}

scanf("%d", &N);
for(int i = 1; i <= N; ++i) {
scanf("%d %d", S + i, T + i);
}

++cur; // node 1 is head, stores (0, 0)
int ans = 0;
for(int i = N; i >= 1; --i) {
++cur;
A[cur] = S[i];
int height = geth();

// search for insertion point of cur
for(int r = MAXH; r >= 0; --r) {
while (nxt[r][x] && A[nxt[r][x]] < A[cur]) x = nxt[r][x];
down(r, x);
}

// compute time when cow i sits
int val = B[x] - A[x] + S[i] + T[i];
B[cur] = val; // insert (A[cur], B[cur]) into queue
if (val > ans) ans = val;

// insert cur into queue
// simultaneously decrement pairs passed by cow i
--A[x];
for(int r = MAXH; r >= 0; --r) {
// search for insertion point while decrementing ranges
while (nxt[r][x] && A[nxt[r][x]] < A[cur]) {
++lazy[r][x];
x = nxt[r][x];
--A[x];
}
down(r, x);

// delete nodes majorized by cur
while (nxt[r][x] && better(cur, nxt[r][x])) {
down(r, nxt[r][x]);
nxt[r][x] = nxt[r][nxt[r][x]];
}

// insert cur depending on layer
if (height >= r) {
nxt[r][cur] = nxt[r][x];
nxt[r][x] = cur;
}
}
--A[cur]; // A[cur] must be decremented too
}

printf("%d\n", ans);
return 0;
}

```