After Prof. TOI has carried out a survey to promote tourism to a certain extent, he discovered that there is a place not far from the city of Phitsanulok that can be interestingly developed to become a natural tourist attraction. The tourist spot is located in Ban Mung, Noen Maprang, Phitsanulok which is considered to be an emerging tourist attraction. Its main attractions are the beautiful landscape and alternately overlapping limestone mountain range. With such a geological feature, it is suitable for sport climbing. Therefore, the villagers in that area have the idea to develop it into a new tourist attraction in the province by organizing a sport climbing competition at Ban Mung 2023 in order to publicize to the general public and give an opportunity for the visitors to challenge themselves by competing in climbing those mountains. The criteria to determine the winner is: the person who gets the highest score from climbing the mountain wins. In order to determine each scoring criteria appropriately, the score will be given based on the mountain that the contestant has climbed, where each mountain, when successfully climbed, gives a certain number of points that will be added to the previous score that the contestant has. The criteria for determining the points of each mountain is judged by the size and the complexity of that mountain. Therefore, the details of the scoring criteria for each mountain is as follows.
- Consider the mountain range by its front view on a 2-dimensional plane.
- The mountain range consists of various mountains, each represented by an isosceles triangle with $$$45^\circ$$$ angle at both sides of its base. Its vertices are located at $$$(L,0), (R,0)$$$, and $$$\left(\frac{R+L}{2},\frac{R-L}{2}\right)$$$, which can be represented as $$$[L, R]$$$ (as shown in Figure 1.)
- Two mountains can be related in the form of parent mountain and child mountain. The $$$i^\text{th}$$$ mountain is a parent mountain of the $$$j^\text{th}$$$ mountain and the $$$j^\text{th}$$$ is a child mountain of the $$$i^\text{th}$$$ mountain when $$$L_i \leq L_j \leq R_j \leq R_i$$$ where $$$[L_i,R_i]$$$ is the location of the $$$i^\text{th}$$$ mountain, and $$$[L_j, R_j]$$$ is the location of the $$$j^\text{th}$$$ mountain, and $$$[L_i, R_i]\neq [L_j, R_j]$$$
- A parent mountain can have more than 1 child mountain
- Denote $$$P(i)$$$ as a scoring function of the $$$i^\text{th}$$$ mountain, then
- $$$P(i) = 1$$$ if the $$$i^\text{th}$$$ mountain doesn't have any child mountain
- $$$P(i) = \max(P(m_1^i), P(m_2^i), \ldots,P(m_{k_i}^i)) + 1$$$ if the $$$i^\text{th}$$$ mountain has $$$k_i$$$ child mountains which are mountains $$$m_1^i, m_2^i, \ldots, m_{k_i}^i$$$, where $$$\max(\cdot)$$$ is a function that returns the maximum value of the numbers.
From the information above, the mountain that has the highest score is going to be the one that Prof. TOI uses as a tourist attraction spot.
Example
Figure 1. An example of parent mountain and child mountain From Figure 1, there are 7 mountains: A, B, C, D, E, F, and G that are located at [2,6], [1,9], [3,8], [6,7], [7,11], [9,13], and [11,13] respectively. We can see that
Mountain B is a parent mountain of mountains A, C, and D (mountains A, C, and D are child mountains of B)
Mountain C is a parent mountain of mountain D (mountain D is a child mountain of mountain C)
Mountain F is a parent mountain of mountain G (mountain G is a child mountain of mountain F)
The score of each mountain can be calculated as follows:
- $$$P(A)$$$,$$$P(D)$$$,$$$P(E)$$$, and $$$P(G)$$$ have a score of 1
- $$$P(C)=\max(P(D))+1=1+1=2$$$
- $$$P(F)=\max(P(G))+1=1+1=2$$$
- $$$P(B)=\max(P(A),P(C),P(D))+1=\max(1,2,1)+1=2+1=3$$$
Your Task
Given the data of every mountain, write an efficient program to determine the score of the mountain with the highest score, and also the score of each mountain.
There are $$$N+1$$$ lines of input:
| Line 1 | An integer $$$N$$$ denoting the number of mountains, for $$$1\leq N\leq 400{,}000$$$ |
| Line $$$i + 1$$$ to Line $$$N+1$$$ where $$$i=1,\ldots,N$$$ | 2 integers separated by a single space, $$$L_i$$$ and $$$R_i$$$, denoting the location $$$[L_i,R_i]$$$ of the $$$i^\text{th}$$$ mountain, where $$$1\leq L_i \leq R_i \leq 10^9$$$ |
There are 2 lines of output:
| Line 1 | Output the score of the mountain with the highest score. |
| Line 2 | Output $$$N$$$ integers separated by a single space, denoting the score of each mountain in order from the $$$1^\text{st}$$$ mountain to the $$$N^\text{th}$$$ mountain. |
Notice
You will receive 40% of the total score if the program only answers the first line of the output correctly.
Notices regarding the test sets are as follows:
| Test Group | Maximum attainable score in this group | Condition(s) |
| 1 | 5 | $$$L_i = 1$$$ for every $$$i$$$ |
| 2 | 3 | $$$L_i$$$ are sorted in an ascending order, and $$$R_i$$$ are sorted in a descending order i.e. $$$L_i-1\leq L_i$$$ and $$$R_i-1\geq R_i$$$ for every integer $$$i=2,\ldots,N$$$ |
| 3 | 4 | $$$L_i$$$ are sorted in an ascending order, and $$$R_i$$$ are also sorted in an ascending order i.e. $$$L_i-1\leq L_i$$$ and $$$R_i-1\leq R_i$$$ for every integer $$$i=2,\ldots,N$$$ |
| 4 | 12 | $$$N\leq 5$$$ |
| 5 | 20 | $$$N\leq 2{,}000$$$ |
| 6 | 23 | The answer of the first question is not greater than 50 |
| 7 | 33 | No additional constraints. |
7 9 13 11 13 7 11 1 9 2 6 3 8 6 7
3 2 1 1 3 1 2 1
5 1 3 1 6 1 5 1 1000 1 4
5 1 4 3 5 2
4 1 2 2 3 3 4 4 5
1 1 1 1 1
Recommended programming tips
If the contestant uses cin/cout, it is recommended to add 2 lines as the following:
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
