K - Raw Power
All submissions for this problem are available.
The University of Geo Tech, Riga has a new doctoral student on the block who calls himself Raw Power. He has N meetings lined up today and wants to avoid them all.
The ith meeting takes place from time units si to ti. Raw power wants to move meetings around so that the amount of time for which all meetings are simultaneously scheduled is maximized. Once he does this, he will send an email to his advisor citing this number to justify the cancellation.
Of course moving meetings around affects a student's credibility. Specifically moving a meeting from time period [si, ti] to [si + a, ti + a] is possible for any integer a but reduces credibility by |a| (|x| denotes absolute value of x). Raw Power currently has a credibility of K and is willing to sacrifice it all. He needs your help to know the maximum possible intersection of all meeting times that he can achieve whilst keeping his credibility non-negative.
Formalizing intersection: Given a set of meetings each with a start and end time, let the maximum start time over all meetings be s and the minimum end time over all meetings be e. The intersection time of all meetings is 0 if s>=e and e-s otherwise.
- The first line contains a single integer N, the total number of meetings scheduled.
- N lines follow, the ith of which contains integers si and ti, the start time and end time of the ith meeting.
- The next line contains a single integer Q, denoting the number of queries.
- Q lines follow, the ith of which contains an integer K denoting the available credibility. Note that all the queries are indepedent.
- Output Q lines, the ith of which should contain a single integer, the answer for test case i. This value denotes the maximum attainable intersection of all meetings under the constraint of available credibility.
- 1 ≤ N ≤ 300000
- 0 ≤ si ≤ ti ≤ 109
- 1 ≤ Q ≤ 20
- 0 ≤ K ≤ 1018
Input: 4 5 10 2 12 14 25 7 19 7 100000 4 5 6 7 8 9 Output: 5 0 1 2 3 4 5
If the total credibility is 6, one way to obtain an intersection of 2 is to move the meeting [14, 25] to [8, 19] so that all meetings intersect in the time range [8, 10].
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.