## Editorial for DMOPC '22 Contest 2 P6 - Yogyakarta Elevators

**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:

Any contiguous subsequence of floors that contains a floor with zero elevators is not reachable. Thus, we will only consider contiguous subsequences in which every floor contains at least one elevator.

Define as the set of elevators which stop within a contiguous subsequence of floors . Notice that is reachable if and only if starting from every elevator in , it is possible to reach all other elevators in . In other words, if we consider each floor as a set of edges between all pairs of elevators that stop at it, is reachable if and only if is a connected graph with edges within .

Rephrasing the question, each floor represents a set of elevators () and edges between elevators (), and we want to find the largest contiguous subsequence such that contains exactly one connected component.

*Observations:*

- Notice that because we only care about connectivity, instead of needing edges for each floor, we can use edges, connecting each elevator on the floor to the leftmost elevator on that floor.
- Notice that starting at each floor , the connected components in for all only changes at most times, times for each introduced elevator, and times for each edge that connects two distinct components. Thus, for each floor , there are at most important floors where the number of connected components changes. In particular, we only care about the first time each elevator appears and the first edges which connect distinct components.
- Let be the first edges which connect distinct components in . Notice that .

*Algorithm:*

Line sweep from to , at each floor maintaining:

- The earliest appearance of each elevator, in order of appearance. This can be done by adding the elevators which appear on floor at the front of the list and then removing duplicates, taking time.
- The first edges which connect distinct components. As each contains at most edges, we can just create a new DSU and add all of the edges in order, noting the edges which connect distinct components, taking time.

Then at each floor, add the important edges and elevators to a DSU in order. If at any point contains only one connected component, the floors after the current update and before the next update creates a reachable contiguous subsequence with and thus should be considered in the final answer. In total, this takes time.

*Note:* Special care should be taken for floors with zero elevators so that we don't consider contiguous subsequences which include them.

**Time Complexity:**

## Comments