Codeforces Round 904 (Div. 2) |
---|
Закончено |
Массив $$$a_1, a_2, \ldots, a_m$$$ изначально заполнен нулями. Вам даны $$$n$$$ попарно различных отрезков $$$1 \le l_i \le r_i \le m$$$. Вы должны выбрать произвольное подмножество этих отрезков (в частности, можно выбрать пустое множество). После этого происходит следующее:
Найдите наибольшую стоимость по всем подмножествам данного множества отрезков.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^9$$$) — количество отрезков и длина массива.
Следующие $$$n$$$ строк каждого набора входных данных описывают отрезки: $$$i$$$-я из них содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$). Гарантируется, что все отрезки попарно различны.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите наибольшую стоимость среди всех подмножеств данного множества отрезков.
61 32 23 82 43 54 66 31 11 21 32 22 33 37 62 21 61 25 61 54 43 66 276 265 172 320 211 2212 244 10000000002 9999999993 1000000000123456789 9876543219274 123456789
1 3 2 3 4 4
В первом наборе входных данных доступен всего один отрезок. Если его не выбирать, то массив будет равен $$$a = [0, 0, 0]$$$, стоимость такого (пустого) подмножества отрезков равна $$$0$$$. Если же выбрать единственный доступный отрезок, то массив станет равен $$$a = [0, 1, 0]$$$, и стоимость будет равна $$$1 - 0 = 1$$$.
Во втором наборе входных данных можно выбрать все отрезки: массив в таком случае будет равен $$$a = [0, 1, 2, 3, 2, 1, 0, 0]$$$. Стоимость будет равна $$$3 - 0 = 3$$$.
Название |
---|