2014D.md (2176B)
1 Source: https://codeforces.com/problemset/problem/2014/D 2 3 D. Robert Hood and Mrs Hood 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Impress thy brother, yet fret not thy mother. 22 23 Robin's brother and mother are visiting, and Robin gets to choose the start day for each visitor. 24 25 All days are numbered from $1$ to $n$. Visitors stay for $d$ continuous days, all of those $d$ days must be between day $1$ and $n$ inclusive. 26 27 Robin has a total of $k$ risky 'jobs' planned. The $i$-th job takes place between days $l_i$ and $r_i$ inclusive, for $1 \le i \le k$. If a job takes place on any of the $d$ days, the visit overlaps with this job (the length of overlap is unimportant). 28 29 Robin wants his brother's visit to overlap with the maximum number of distinct jobs, and his mother's the minimum. 30 31 Find suitable start days for the visits of Robin's brother and mother. If there are multiple suitable days, choose the earliest one. 32 33 Input 34 35 The first line of the input contains a single integer $t$ ($1\leq t \leq 10^4$) — the number of test cases. 36 37 The first line of each test case consists of three integers $n$, $d$, $k$ ($1 \le n \le 10^5, 1 \le d, k \le n$) — the number of total days, duration of the visits, and the number of jobs. 38 39 Then follow $k$ lines of each test case, each with two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the start and end day of each job. 40 41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 42 43 Output 44 45 For each test case, output two integers, the best starting days of Robin's brother and mother respectively. Both visits must fit between day $1$ and $n$ inclusive. 46 47 Example 48 49 Input 50 51 ``` 52 6 53 54 2 1 1 55 56 1 2 57 58 4 1 2 59 60 1 2 61 62 2 4 63 64 7 2 3 65 66 1 2 67 68 1 3 69 70 6 7 71 72 5 1 2 73 74 1 2 75 76 3 5 77 78 9 2 1 79 80 2 8 81 82 9 2 4 83 84 7 9 85 86 4 8 87 88 1 3 89 90 2 3 91 ``` 92 93 Output 94 95 ``` 96 1 1 97 2 1 98 1 4 99 1 1 100 1 1 101 3 4 102 ``` 103 104 Note 105 106 In the first test case, the only job fills all $2$ days, both should visit on day $1$. 107 108 In the second test case, day $2$ overlaps with $2$ jobs and day $1$ overlaps with only $1$. 109 110 In the third test case, Robert visits for days $[1,2]$, Mrs. Hood visits for days $[4,5]$.