Multi-Colored Segments
Contest: Codeforces Round 826 (Div. 3)
Difficulty rating: 2000
Tags: binary search, data structures, math, sortings

Dmitry has $$$n$$$ segments of different colors on the coordinate axis $$$Ox$$$. Each segment is characterized by three integers $$$l_i$$$, $$$r_i$$$ and $$$c_i$$$ ($$$1 \le l_i \le r_i \le 10^9, 1 \le c_i \le n$$$), where $$$l_i$$$ and $$$r_i$$$ are are the coordinates of the ends of the $$$i$$$-th segment, and $$$c_i$$$ is its color.

Dmitry likes to find the minimum distances between segments. However, he considers pairs of segments of the same color uninteresting. Therefore, he wants to know for each segment the distance from this segment to the nearest differently colored segment.

The distance between two segments is the minimum of the distances between a point of the first segment and a point of the second segment. In particular, if the segments intersect, then the distance between them is equal to $$$0$$$.

For example, Dmitry has $$$5$$$ segments:

- The first segment intersects with the second (and these are segments of different colors), so the answers for them are equal to $$$0$$$.
- For the $$$3$$$-rd segment, the nearest segment of a different color is the $$$2$$$-nd segment, the distance to which is equal to $$$2$$$.
- For the $$$4$$$-th segment, the nearest segment of a different color is the $$$5$$$-th segment, the distance to which is equal to $$$1$$$.
- The $$$5$$$-th segment lies inside the $$$2$$$-nd segment (and these are segments of different colors), so the answers for them are equal to $$$0$$$.

Input format:
The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.

The descriptions of the test cases follow.

The first line of description of each test case contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of segments.

The next $$$n$$$ lines contain descriptions of the segments. Each segment is described by three integers $$$l_i$$$, $$$r_i$$$ and $$$c_i$$$ ($$$1 \le l_i \le r_i \le 10^9, 1 \le c_i \le n$$$) — coordinates of the left and right ends of $$$i$$$-th segment, as well as the color of this segment. It is guaranteed that there are at least $$$2$$$ segments of different colors.

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

Output format:
For each test case, on a separate line print $$$n$$$ integers, where the $$$i$$$-th number is equal to the distance from the $$$i$$$-th segment to the nearest segment of a different color.

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

Note:
In the first test case of the first sample there is only one segment of color $$$2$$$, and all other segments have color $$$1$$$. Therefore, for segments of color $$$1$$$, the answer is equal to the distance to the $$$3$$$rd segment, and for $$$3$$$rd one, the answer is equal to the minimum of the distances to segments of color $$$1$$$.

In the second test case of the first sample there are only $$$2$$$ segments, and for both of them the answer is equal to the distance between them.

In the third test case of the first sample, each segment intersects at least one of its ends with a segment of a different color, so all answers are equal to $$$0$$$.

The fourth test case of the first sample is described in the problem statement.

In the fifth test case of the first sample, one segment lies completely inside the other, and for both of them the answer is $$$0$$$.

In the sixth test case of the first sample, all segments are points of different colors.

Example input:
9
3
1 2 1
3 4 1
5 6 2
2
100000000 200000000 1
900000000 1000000000 2
5
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
5
1 5 1
4 9 2
1 2 1
8 9 2
5 7 3
2
1 100 2
10 90 1
3
1 1 1
10 10 2
1000000000 1000000000 3
3
3 4 1
2 5 1
1 6 2
6
5 6 2
11 12 3
7 8 2
3 4 2
1 2 1
9 10 2
2
1 3 1
2 3 2

Example output:
3 1 1 
700000000 700000000 
0 0 0 0 0 
0 0 2 1 0 
0 0 
9 9 999999990 
0 0 0 
3 1 3 1 1 1 
0 0

Example input:
4
8
11 16 7
12 15 7
2 5 8
17 22 5
1 8 8
19 23 8
16 16 6
6 7 5
9
1 4 3
5 11 1
8 11 3
1 10 1
2 11 1
1 10 4
3 11 1
5 7 1
1 11 1
9
25 25 1
26 26 1
24 24 2
13 14 2
12 16 2
17 18 1
19 19 1
24 27 2
24 27 1
9
15 18 1
20 22 2
13 22 2
13 22 2
3 13 2
6 10 2
3 6 2
19 24 2
22 24 2

Example output:
0 1 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 3 1 1 3 0 0 
0 2 0 0 2 5 9 1 4

Editorial:
Let's go through the segments $$$2$$$ times: in non-decreasing coordinates of the left end, and then — in non-increasing coordinates of the right end. To walk a second time, just multiply the coordinates of the left and right borders by $$$-1$$$, and then swap them and walk from left to right.
Going through the segments in non-decreasing coordinates of the left end, you need to find for each segment a segment that starts not to the right of the current one and ends as far to the right as possible. If the coordinate of its right end is not less than the coordinate of the left end of the current segment, then it intersects with it, otherwise the distance between them is equal to the distance between the coordinate of the left end of the current segment and the maximum coordinate of the right end of the segment starting to the left of ours.
Note that it is enough for us to store no more than $$$2$$$ segments: for each color we will store the maximum right coordinate of the segment of this color, which has already been considered. If we store the $$$2$$$ colors with the largest right coordinates, then one of them is definitely not equal to the current one. When considering a segment, we add it to the list, and if the size of the list becomes $$$3$$$, then we leave $$$2$$$ of optimal elements.