National Olympiad in Informatics, China, 2011
NOI 2011 at Jilin University has started! To welcome outstanding informatics competitors from across the country, Jilin University has decided to host two magnificent NOI carnivals at two different venues. Each venue contains many different events, and each event can only be held in one of the venues.
Little Andy, the carnival event organizer, has received a total of event applications. The -th event starts at and has a duration of . Each event may be scheduled at any one venue, or not scheduled at all.
After extensive surveying, Andy discovered that at any given time, if both venues are simultaneously hosting events (excluding the instant when events start or end), competitors will be distraught over deciding between which venue to attend. To prevent this unpleasant scenario, Andy requires that no two events may be simultaneously held at both venues. Multiple events at the same venue may be held as pleased.
As one may imagine, if a certain venue contains too few events, then its appeal will not be so great, leading to a deserted site. Andy wishes to make an appropriate schedule such that the number of events at the venue with the fewest events is as large as possible.
Additionally, some events are very interesting and Andy would like to try to host them. He wishes to know, if the -th event must be held (it may be held at either one of the venues), what is the maximum number of events that can be held at the venue with the fewest events.
Input Specification
The first line contains an integer , representing the number of
events.
For the following lines, each line describes a single event. The
-th of these lines contains two integers and ,
indicating that event will start at and last units
of time.
Output Specification
The first line of output should contain a single integer, representing
the maximum number of events that can be held at the venue with the
fewest events, without any extra restrictions about which event must be
held.
The following lines should each contain a single integer. The -th
of these lines should contain the maximum number of events that can be
held at the venue with the fewest events, under the precondition that
event must be held.
Sample Input
5
8 2
1 5
5 3
3 2
5 3
Sample Output
2
2
1
2
2
2
Explanation
When there are no extra constraints, events and should be scheduled at one venue, and events and should be scheduled at the other venue. Event is not scheduled.
Scoring
For each test case, your score out of is determined as follows:
- If the output format is invalid (e.g. there are fewer than lines), then your score will be .
- If the first line is incorrect, and at least one of the following lines is incorrect, then your score will be .
- If the first line is correct, but at least one of the following lines is incorrect, then your score will be .
- If the first line is incorrect, but all of the following lines are correct, then your score will be .
- If all lines in the output are correct, then your score will be .
Constraints
The attributes of all the test cases are outlined below.
Test Case | Range of | Constraints |
---|---|---|
Problem translated to English by .
Comments