|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
1559. Gnawed books
|
| View Problem Statistics | Submit | Problem added 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
|
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Problems from Contests and Camps / | Trainings in Perm 2009 / | 06.07.09 Big Contest / |
| 1558. G - Timetable | 1559. |
| time generating 0.859 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |