Andrey and Escape from Capygrad
Contest: Codeforces Round 892 (Div. 2)
Difficulty rating: 1800
Tags: binary search, data structures, dp, dsu, greedy, sortings

An incident occurred in Capygrad, the capital of Tyagoland, where all the capybaras in the city went crazy and started throwing mandarins. Andrey was forced to escape from the city as far as possible, using portals.

Tyagoland is represented by a number line, and the city of Capygrad is located at point $$$0$$$. There are $$$n$$$ portals all over Tyagoland, each of which is characterised by four integers $$$l_i$$$, $$$r_i$$$, $$$a_i$$$ and $$$b_i$$$ ($$$1 \le l_i \le a_i \le b_i \le r_i \le 10^9$$$). Note that the segment $$$[a_i, b_i]$$$ is contained in the segment $$$[l_i, r_i]$$$.

If Andrey is on the segment $$$[l_i, r_i]$$$, then the portal can teleport him to any point on the segment $$$[a_i, b_i]$$$. Andrey has a pass that allows him to use the portals an unlimited number of times.

Andrey thinks that the point $$$x$$$ is on the segment $$$[l, r]$$$ if the inequality $$$l \le x \le r$$$ is satisfied.

Andrey has $$$q$$$ options for where to start his escape, each option is characterized by a single integer $$$x_i$$$ — the starting position of the escape. He wants to escape from Capygrad as far as possible (to the point with the maximum possible coordinate). Help Andrey determine how far he could escape from Capygrad, starting at each of the $$$q$$$ positions.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of sets of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of portals.

Each of the next $$$n$$$ lines contains four integers $$$l_i$$$, $$$r_i$$$, $$$a_i$$$, and $$$b_i$$$ $$$(1 \le l_i \le a_i \le b_i \le r_i \le 10^9)$$$ — the characteristics of the portals.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of positions.

The following line contains $$$q$$$ integers $$$x_1, x_2, \ldots, x_q$$$ ($$$1 \le x_i \le 10^9$$$) — the position from which Andrey will start his escape in the $$$i$$$-th options.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single line of $$$q$$$ integers, containing the answers to Andrey's questions.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case:

Optimal actions when starting from each position:

1. Use portal $$$1$$$ and teleport to point $$$b_1 = 14$$$.
2. Use portal $$$2$$$ first and teleport to point $$$6$$$, which is on the segment $$$[l_1, r_1] = [6, 17]$$$, then use portal $$$1$$$ and teleport to point $$$b_1 = 14$$$.
3. Stay at point $$$x_3=23$$$ without using any portals.
4. Stay at point $$$x_4=15$$$ without using any portals.
5. Point $$$x_5=28$$$ is not on any segment, so Andrey won't be able to teleport anywhere.
6. Point $$$x_6=18$$$ is only on the segment $$$[l_3, r_3] = [16, 24]$$$, use portal $$$3$$$ and teleport to point $$$b_3 = 22$$$.

In the fifth test case:

Optimal actions when starting from each position:

1. Use portal $$$1$$$ first and teleport to point $$$15$$$ on the segment $$$[a_1, b_1] = [14, 20]$$$, then use portal $$$2$$$ and teleport to point $$$21$$$, which is on the segment $$$[l_4, r_4] = [21, 33]$$$ and on the segment $$$[a_2, b_2] = [13, 24]$$$, then teleport to point $$$b_4 = 32$$$.
2. Use portal $$$6$$$ first and teleport to point $$$20$$$ on the segment $$$[a_6, b_6] = [20, 21]$$$, then use portal $$$2$$$ and teleport to point $$$22$$$, which is simultaneously on the segment $$$[l_4, r_4] = [21, 33]$$$ and on the segment $$$[a_2, b_2] = [13, 24]$$$, then teleport to point $$$b_4 = 32$$$.
3. Perform the same actions as from the first position.
4. Stay at point $$$x_4=5$$$ without using any portals.
5. Point $$$8$$$ is not on any segment, so Andrey won't be able to teleport anywhere.
6. Stay at point $$$x_6=33$$$ without using any portals.
7. Use portal $$$5$$$ and teleport to point $$$b_5 = 4$$$.
8. Perform the same actions as from the first position.

Example input:
5
3
6 17 7 14
1 12 3 8
16 24 20 22
6
10 2 23 15 28 18
3
3 14 7 10
16 24 20 22
1 16 3 14
9
2 4 6 8 18 23 11 13 15
2
1 4 2 3
3 9 6 7
3
4 8 1
5
18 24 18 24
1 8 2 4
11 16 14 14
26 32 28 30
5 10 6 8
9
15 14 13 27 22 17 31 1 7
6
9 22 14 20
11 26 13 24
21 33 22 23
21 33 25 32
1 6 3 4
18 29 20 21
8
11 23 16 5 8 33 2 21

Example output:
14 14 23 15 28 22 
14 14 14 14 22 23 14 14 15 
7 8 7 
15 14 14 30 24 17 31 4 8 
32 32 32 5 8 33 4 32

Editorial:
Statement: It is always beneficial to teleport to point $$$b_i$$$.
Proof: Let's assume that we were able to teleport from point $$$X$$$ to the right of $$$b_i$$$, but not from $$$b_i$$$. Then we used some segment $$$A$$$ that covers point $$$X$$$, but does not cover point $$$b$$$, and ends to the right of $$$b$$$. This is a contradiction.
Let $$$ans_i$$$ be the maximum coordinate we can reach while being on segment $$$i$$$, and let $$$p_j$$$ be the answer to the $$$j$$$-th query. Then we notice that the answer to query $$$p_j = \max(x_j, \max_{i = 1}^n \{ans_i \vert l_i \le x_j \le r_i\})$$$.
We will use the scanline method from the end. Events: $$$l_i$$$, $$$b_i$$$, $$$r_i$$$, $$$x_j$$$.
We notice that events of type $$$r_i$$$ are not important to us when scanning from the end (according to statement number 1). It is important for us that we process events of type $$$b_i$$$ first, then events of type $$$x_j$$$, and then events of type $$$l_i$$$ (closing the segment in the scanline).
We will go through the events of the scanline, processing them in the order of $$$b_i$$$, then events of type $$$x_j$$$, and then events of type $$$l_i$$$.
We assume that there is a data structure that allows us to add elements, remove elements, and quickly output the maximum.
• For each event of type $$$b_i$$$, update the value of $$$ans_i$$$ - take the maximum value of $$$ans$$$ of all open segments from the structure.
• For each event of type $$$x_j$$$, update the value of $$$p_j$$$ - take the maximum value of $$$ans$$$ of all open segments from the structure, as well as $$$x_j$$$.
• For each event of type $$$l_i$$$, remove $$$ans_i$$$ from the structure.
We notice that to solve this problem, we can use the $$$\bf{std::multiset}$$$ container, which automatically sorts elements in ascending order. We can store in $$$multiset$$$ $$$ans_i$$$ of all open segments. And then, when processing events, extract the maximum from $$$multiset$$$, all operations are performed in $$$O(\log n)$$$. This allows us to solve the problem in $$$O((n + q) \log n)$$$ time and $$$O(n)$$$ memory.