codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]$.