|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
1559. Изгрызенные книги
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
— Тысяча червей! из диалога преферансистов
Санкт-Петербургский Государственный Университет славится, в частности, своей библиотекой. Однако, другой известный университет из зависти запустил в библиотеку СПбГУ книжных червей. Теперь главному библиотекарю (его, кстати говоря, зовут Вася) нужно срочно определить величину ущерба. Все N книг в библиотеке хранятся на одной очень длинной полке. Посмотрев на корешок, Вася может определить номер книги, не трогая её руками. Книги пронумерованы слева направо, начиная с единицы. Ни одна книга не перевёрнута вверх тормашками. Вася обнаружил в библиотеке M червей. Он определил, где каждый червь начал и где закончил свой путь. Все черви двигались прямолинейно слева направо или справа налево. Чтобы правильно посчитать ущерб, нанесённый библиотеке, Вася хочет написать программу, вычисляющую, сколько страниц изгрызло ровно k червей. Помогите ему это сделать. Входные данные В первой строке входного файла заданы через пробел два числа N и M (1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Вторая строка содержит N положительных целых чисел pi — количество страниц в i-й книге (pi ≤ 10000). В следующих M строках содержатся описания путей. Описание пути состоит из четырёх положительных целых чисел — номер книги и номер страницы начала пути червя, а также номер книги и номер страницы окончания пути червя. Выходные данные Выходной файл должен содержать (M+1) строк. В k-й строке выведите количество страниц, которые изгрызло ровно (k-1) червей. Пример Входные данные 3 2 Выходные данные 0
|
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи с соревнований и сборов / | Сборы в Перми 2009 / | 06.07.09 Большой контест / |
| 1558. G - Расписание | 1559. |
| время генерации 0.594 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |