Задача №113823. Потоки
| Ограничение по времени, сек | 0.7 |
| Ограничение по памяти, мегабайт | 256 |
В городе Рязань весьма специфический водопровод. Он представляет из себя одну длинную трубу проходящую через N + 1 узел, занумерованный от 0 до N . Каждый отсек трубы имеет пропускную способность не более K литров. Из-за технических работ, связанных с древнерусской традицией отключения горячей воды летом, коммунальным службам города иногда требуется начать перекачивать по литру воды в секунду от узла L до узла R . Так как пропускная способность трубы ограниченна, с учётом всех предыдущих перекачек это не всегда возможно. Требуется на каждый запрос отвечать, можно ли пропустить поток воды между двумя узлами, и если это возможно, пустить её между этими узлами.
В первой строке содержаться три числа N — количество узлов ( 1 ≤ N ≤ 200 000 ), K — максимальная пропускная способность каждого отсека трубы ( 1 ≤ K ≤ 1000 ) и M — количество запросов ( 1 ≤ M ≤ 100 000 ). В следующих M строках описаны запросы, каждый из которых состоит из двух чисел L и R ( 0 ≤ L < R ≤ N ).
На каждый запрос ваша программа должна выдавать результат в виде числа 0 если поток пустить нельзя и 1 , если это получилось. Каждый результат должен быть на отдельной строке
Программа, верно работающая при N ≤ 100 , будет оцениваться в 30 баллов.
5 2 4 0 4 1 2 1 4 2 4
1 1 0 1