2028 : The Siruseri Convention Centre
Problem type : Batch
Time limit : 1.5 second(s)
Memory limit : 64 megabyte(s)
Problem type : Batch
Time limit : 1.5 second(s)
Memory limit : 64 megabyte(s)
The Government of Siruseri has constructed a new Convention Centre. A number of companies have expressed an interest in renting the auditorium in the Convention Centre to hold their conferences.
A client is willing to rent the auditorium only if it is granted to him exclusively for the entire duration of his conference. The marketing head of the Convention Centre has decided that the best strategy would be to rent the auditorium out to as many different clients as possible. Clearly there may be more than one way to do this.
Consider, for instance, the following example with 4 companies. The companies are listed in the order in which they made requests for the auditorium, with the duration of each conference indicated by the starting and ending day.
In this example, it is possible to rent out the auditorium to a maximum of two companies. The choices are 1 and 3, or 2 and 3, or 1 and 4. Note that the auditorium can be rented out to only one company on any day. Thus, 1 and 2 cannot both be granted the auditorium because their requests overlap on day 9.
The marketing head believes in fairness and he has decided on the following procedure to choose the combination to which he will rent out the auditorium. A set of requests is a candidate to be chosen if it is of maximum size. Observe that the companies are numbered according to the order in which they make their requests. The companies in each candidate set are listed out in ascending order. Among these, the lexicographically smallest candidate set is chosen. (Lexicographic order is dictionary order, so list l1 is smaller than list l2 if l1 is a prefix of l2 or if at the first position j where l1 and l2 differ, l1[j] < l2[j].)
In this example the auditorium will be rented out to companies 1 and 3 - the three candidate sets are {(1, 3), (2, 3), (1, 4)} and (1, 3) < (1, 4) < (2, 3) when ordered lexicographically.
Task
Your task is to help the marketing head decide the set of companies to which the auditorium is to be rented.
Input format
The first line contains an integer N, the number of companies that have applied for renting the auditorium. Lines 2 to N+1 contain two integers. The integers on line i+1 are the starting and ending dates for the request from company i.
Output format
The first line of the output should consist of an integer M, the maximum number of companies to which the auditorium can be rented. This should be followed by a line containingM integers listing the identities of the companies that appear in the lexicographically smallest such set.
Test Data
In 50% of the inputs, N <= 3,000. In all inputs, N <= 200,000. For each company's request, the starting day is always greater than or equal to 1 and the ending day never exceeds 109.
Reference: Asia-Pacific Informatics Olympiad 2009
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
A client is willing to rent the auditorium only if it is granted to him exclusively for the entire duration of his conference. The marketing head of the Convention Centre has decided that the best strategy would be to rent the auditorium out to as many different clients as possible. Clearly there may be more than one way to do this.
Consider, for instance, the following example with 4 companies. The companies are listed in the order in which they made requests for the auditorium, with the duration of each conference indicated by the starting and ending day.
In this example, it is possible to rent out the auditorium to a maximum of two companies. The choices are 1 and 3, or 2 and 3, or 1 and 4. Note that the auditorium can be rented out to only one company on any day. Thus, 1 and 2 cannot both be granted the auditorium because their requests overlap on day 9.
The marketing head believes in fairness and he has decided on the following procedure to choose the combination to which he will rent out the auditorium. A set of requests is a candidate to be chosen if it is of maximum size. Observe that the companies are numbered according to the order in which they make their requests. The companies in each candidate set are listed out in ascending order. Among these, the lexicographically smallest candidate set is chosen. (Lexicographic order is dictionary order, so list l1 is smaller than list l2 if l1 is a prefix of l2 or if at the first position j where l1 and l2 differ, l1[j] < l2[j].)
In this example the auditorium will be rented out to companies 1 and 3 - the three candidate sets are {(1, 3), (2, 3), (1, 4)} and (1, 3) < (1, 4) < (2, 3) when ordered lexicographically.
Task
Your task is to help the marketing head decide the set of companies to which the auditorium is to be rented.
Input format
The first line contains an integer N, the number of companies that have applied for renting the auditorium. Lines 2 to N+1 contain two integers. The integers on line i+1 are the starting and ending dates for the request from company i.
Output format
The first line of the output should consist of an integer M, the maximum number of companies to which the auditorium can be rented. This should be followed by a line containingM integers listing the identities of the companies that appear in the lexicographically smallest such set.
Test Data
In 50% of the inputs, N <= 3,000. In all inputs, N <= 200,000. For each company's request, the starting day is always greater than or equal to 1 and the ending day never exceeds 109.
Reference: Asia-Pacific Informatics Olympiad 2009
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 4 4 9 9 11 13 19 10 17 | 2 1 3 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 15 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)