Codeforces Round 906 (Div. 1) |
---|
Закончено |
Единственное различие между двумя версиями этой задачи — ограничение на $$$k$$$, ограничение по времени и ограничение по памяти. Делать взломы можно только в том случае, если решены обе версии задачи.
Дореми живет в дождливой стране, состоящей из $$$n$$$ городов, пронумерованных от $$$1$$$ до $$$n$$$.
По метеорологической трансляции было предсказано распределение дождей в ближайшие $$$m$$$ дней. В $$$i$$$-й день дождь пойдет в городах, находящихся на отрезке $$$[l_i, r_i]$$$. Город называется сухим, если в ближайшие $$$m$$$ дней в нем не будет дождя.
Оказалось, что Дореми обладает особой способностью. Она может выбрать $$$k$$$ (в простой версии: $$$k = 2$$$) дней, и в течение этих дней дождя не будет. Дореми хочет вычислить максимальное количество сухих городов после использования специальной силы.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$2 \le m \le 2\cdot 10^5$$$, $$$k = 2$$$) — количество городов, количество дней и количество дней дождя, которые может предотвратить Дореми.
Далее следуют $$$m$$$ строк. В $$$i$$$-й строке содержатся два целых числа $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — отрезок городов, в которых будет дождь в день $$$i$$$.
Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — максимальное количество сухих городов.
62 3 21 21 21 15 3 21 32 43 510 6 21 56 102 23 75 81 4100 6 21 1001 1001 1001 1001 1001 1001000 2 21 11 120 5 29 203 310 1111 136 18
1 2 3 0 1000 15
В первом наборе входных данных, если Дореми использует свою силу в дни
Таким образом, существует не более $$$1$$$ сухого города.
Во втором наборе входных данных, если Дореми предотвращает
Таким образом, существует не более $$$2$$$ сухих городов.
В третьем наборе входных данных оптимальным является предотвращение дождя в дни $$$2,5$$$.
В четвертом наборе входных данных всегда есть $$$4$$$ дня дождя, которые промочат все города, вне зависимости от использования силы.
Название |
---|