First, let us sort out the conditions. Assume that:

• \(A_i < B_i\)
• \(A_1, B_1, A_2, B_2 \cdots, A_N, B_N\) are all different.

Let us say that the person who got on at Floor \(1\) gets off at Floor \(x\). Then, we can see that the persons who got on at Floor \(2, 3, \cdots, x-1\) get off at Floor \(x + 1, x + 2, \cdots, 2x-2\).

By repeating this argument, we can see that the condition is satisfied if and only if it is possible to divide the \(2N\) floors into segments where the persons with \((A, B) = (x, x+k), (x+1, x+k+1), \cdots, (x+k-1, x+2k-1)\) get on and off.

Now, let us think of a way to determine, for a fixed division, if it is possible to fill in \(A\) and \(B\) so that the above holds.

Let us make an array that stores (left/right, the person’s ID) for each floor if there is a person bound to get on/off on that floor.

For each segment, the following is necessary:

• There is no person with fixed \(A\) and \(B\) such that only one of them is contained in the segment. If a person has both \(A\) and \(B\) in the segment, they are in the correct positions.
• If the persons who got on/off at Floor \(x+i\)/\(x+k+i\) are both already fixed, they are the same person.
• There is no pair of floors (\(x+i\), \(x+k+i\)) such that the person at Floor \(x+i\) is “left.”
• There is no pair of floors (\(x+i\), \(x+k+i\)) such that the person at Floor \(x+k+i\) is “right.”

On the other hand, if the above is satisfied for every segment, we can find one correct record by filling in \(A\) and \(B\) properly.

Thus, the problem can be solved by DP. Let dp[\(i\)]:= (true if a segment ends exactly at Floor \(i\) and there is no contradiction until Floor \(i\), false otherwise), and make dp[\(r\)] true when a new segment \([i+1, r]\) has no contradiction.

The time complexity is \(\mathrm{O}(N^3)\).

Sample Implementation (added on July 8 (Japan time))

Sample Misimplementation (turned out to be wrong later)