[Solution] Multi-Colored Segments solution codeforces

Table of Contents

Multi-Colored Segments solution codeforces

Multi-Colored Segments solution codeforces – Dmitry has 𝑛n segments of different colors on the coordinate axis 𝑂𝑥Ox. Each segment is characterized by three integers 𝑙𝑖li𝑟𝑖ri and 𝑐𝑖ci (1𝑙𝑖𝑟𝑖109,1𝑐𝑖𝑛1≤li≤ri≤109,1≤ci≤n), where 𝑙𝑖li and 𝑟𝑖ri are are the coordinates of the ends of the 𝑖i-th segment, and 𝑐𝑖ci 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 00.

[Solution] Multi-Colored Segments solution codeforces

For example, Dmitry has 55 segments:

Multi-Colored Segments solution codeforces

  • The first segment intersects with the second (and these are segments of different colors), so the answers for them are equal to 00.
  • For the 33-rd segment, the nearest segment of a different color is the 22-nd segment, the distance to which is equal to 22.
  • For the 44-th segment, the nearest segment of a different color is the 55-th segment, the distance to which is equal to 11.
  • The 55-th segment lies inside the 22-nd segment (and these are segments of different colors), so the answers for them are equal to 00.
Input

The first line of the input contains an integer 𝑡t (1𝑡1041≤t≤104) — 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𝑛21052≤n≤2⋅105) — the number of segments.

The next 𝑛n lines contain descriptions of the segments. Each segment is described by three integers 𝑙𝑖li𝑟𝑖ri and 𝑐𝑖ci (1𝑙𝑖𝑟𝑖109,1𝑐𝑖𝑛1≤li≤ri≤109,1≤ci≤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 22 segments of different colors.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105.

[Solution] Multi-Colored Segments solution codeforces

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.

Examples

input

Copy
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

[Solution] Multi-Colored Segments solution codeforces

Copy
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 

input

Copy
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

output

Copy
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 

[Solution] Multi-Colored Segments solution codeforces

In the first test case of the first sample there is only one segment of color 22, and all other segments have color 11. Therefore, for segments of color 11, the answer is equal to the distance to the 33rd segment, and for 33rd one, the answer is equal to the minimum of the distances to segments of color 11.

In the second test case of the first sample there are only 22 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 00.

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 00.

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

In the seventh test case of the first sample, the second segment is a point and is inside the first one, so for both segments the answer is 00.

Leave a Comment