Задача №115397. Пересменка в Сириусе
Участники образовательных программ иногда задумываются, почему между двумя программами обычно бывает перерыв в несколько дней. Ответ прост: сотрудникам Сириуса необходимо после очередной программы привести в порядок жилые номера.
На одном этаже в гостинице ОЦ «Сириус» находятся \(n\) номеров, пронумерованных от \(1\) до \(n\). После проведения образовательной программы все эти номера нуждаются в ремонте.
К ремонтным работам привлечены \(k\) сотрудников, пронумерованных от \(1\) до \(k\). За \(i\)-м сотрудником закреплён диапазон номеров с \(l_i\) по \(r_i\) включительно, а также зафиксирован номер \(m_i\) из этого диапазона, с которого он должен начать обход своих номеров. Диапазоны номеров у разных сотрудников могут пересекаться и даже совпадать.
Сотрудники в некотором порядке направляются с базы для выполнения работ. Следующий сотрудник направляется только после возвращения предыдущего на базу.
Когда \(i\)-го сотрудника направляют на выполнение работ, он сначала идёт в номер \(m_i\). Если этот номер всё ещё нуждается в ремонте, то сотрудник ремонтирует его, а также посещает все номера из диапазона с \(l_i\) по \(r_i\), за который он отвечает, и ремонтирует все нуждающиеся в ремонте номера из этого диапазона, после чего возвращается на базу. После этого все номера из диапазона с \(l_i\) по \(r_i\) более не нуждаются в ремонте.
Если же первый посещённый сотрудником номер \(m_i\) не нуждается в ремонте, поскольку его уже отремонтировали ранее направленные для выполнения работ коллеги, то сотрудник сразу возвращается на базу, надеясь, что коллеги уже отремонтировали и все остальные номера из его диапазона. В этом случае некоторые другие номера из диапазона с \(l_i\) по \(r_i\) всё еще могут нуждаться в ремонте.
Определите, можно ли при подобном подходе сотрудников к выполнению своих обязанностей направить их всех для выполнения работ в таком порядке, чтобы в итоге все номера от \(1\) до \(n\) оказались отремонтированы.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число \(t\) (\(1 \leqslant t \leqslant 10^5\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа \(n\) и \(k\) (\(1 \leqslant n, k \leqslant 5 \cdot 10^5\)) — количество номеров и количество сотрудников соответственно.
В каждой из последующих \(k\) строк содержится три целых числа \(l_i\), \(m_i\) и \(r_i\) (\(1 \leqslant l_i \leqslant m_i \leqslant r_i \leqslant n\)) — первый номер диапазона ответственности \(i\)-го сотрудника, номер из диапазона, с которого он должен начать обход своих, и последний номер из его диапазона, соответственно.
Гарантируется, что сумма \(n\) и \(k\) по всем наборам входных данных не превосходит \(5 \cdot 10^5\).
Для каждого набора входных данных в отдельной строке выведите « YES », если можно отремонтировать все номера, и « NO » — в противном случае.
Обозначим за \(N\) сумму \(n\) по всем наборам входных данных, за \(K\) — сумму \(k\) по всем наборам входных данных.
| Дополнительные ограничения | |||||
| Подзадача | Баллы | \(n\), \(N\) | \(k\), \(K\) | дополнительно | Необх. подзадачи |
| 1 | 5 | – | \(K \leqslant 10\,000\) | \(m_i=l_i\) | |
| 2 | 5 | \(N \leqslant 500\) | \(k \leqslant 8\) | У | |
| 3 | 2 | \(n \leqslant 18\) | \(K \leqslant 500\) | У | |
| 4 | 12 | \(n \leqslant 50\) | \(K \leqslant 50\) | У | |
| 5 | 9 | \(n \leqslant 150\) | \(K \leqslant 150\) | У, 4 | |
| 6 | 8 | \(N \leqslant 500\) | \(K \leqslant 500\) | У | |
| 7 | 6 | – | \(K \leqslant 10\,000\) | За каждым сотрудником закреплен номер 1 или номер \(n\) | – |
| 8 | 18 | – | \(K \leqslant 10\,000\) | Для каждого сотрудника найдется номер, который закреплён только за ним | – |
| 9 | 3 | – | – | Для каждого сотрудника найдется номер, который закреплён только за ним | 8 |
| 10 | 4 | – | \(K \leqslant 10\,000\) | \(r_i-l_i=r_j-l_j\) для любых \(i\), \(j\) | – |
| 11 | 4 | – | \(K \leqslant 10\,000\) | Любое \(m_i\) совпадает с \(l_i\) или \(r_i\) | 1 |
| 12 | 4 | \(n \leqslant 10\,000\) | \(K \leqslant 10\,000\) | – | У, 2–6 |
| 13 | 6 | – | \(K \leqslant 10\,000\) | У, 1–8, 10–12 | |
| 14 | 14 | – | – | У, 1–13 | |
В первом наборе входных данных из примера нужно сначала направить для выполнения ремонтных работ второго сотрудника, он отремонтирует номера с первого по третий. Затем первый сотрудник направится в номер 4. Так как он еще нуждается в ремонте, первый сотрудник отремонтирует оставшиеся номера в своем диапазоне. В результате все номера будут отремонтированы.
Во втором наборе данных выбрать подходящий порядок отправки сотрудников невозможно.
2 5 2 3 4 5 1 3 3 5 3 1 2 4 2 4 5 3 3 3
YES NO