Codeforces Round 964 (Div. 4) |
---|
Закончено |
Как студент факультета компьютерных наук, Алекс сталкивается с трудной задачей — принятием душа. Он старается принимать душ ежедневно, но, несмотря на все его усилия, всегда возникают препятствия. Ему требуется $$$s$$$ минут, чтобы принять душ, а в сутках всего $$$m$$$ минут!
У него уже запланировано $$$n$$$ задач на день. Задача $$$i$$$ представлена интервалом $$$(l_i$$$, $$$r_i)$$$, что означает, что Алекс занят и не может принять душ в этот временной интервал (в любой момент времени строго между $$$l_i$$$ и $$$r_i$$$). Ни одна из задач не пересекается с другой.
Учитывая все $$$n$$$ временных интервалов, сможет ли Алекс принять душ в этот день? Другими словами, будет ли у Алекса свободный временной интервал длиной не менее $$$s$$$?
В первом примере Алекс может принять душ в первые $$$3$$$ минуты дня и не пропустить ни одну из задач.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$s$$$ и $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq s, m \leq 10^9$$$) — количество временных интервалов, которые Алекс уже запланировал, время, необходимое Алексу для принятия душа, и количество минут в сутках.
Затем следуют $$$n$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \leq l_i < r_i \leq m$$$) — временной интервал $$$i$$$-й задачи. Ни одна из задач не накладывается на другую.
Дополнительное ограничение на входные данные: $$$l_i > r_{i-1}$$$ для каждого $$$i > 1$$$.
Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите «YES» (без кавычек), если Алекс может принять душ для данного набора входных данных, и «NO» (также без кавычек) в противном случае.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes», и «Yes» будут признаны положительным ответом).
43 3 103 56 89 103 3 101 23 56 73 3 101 23 56 83 4 101 26 78 9
YES YES NO YES
Название |
---|