0017. Старый забор

Имя входного файла:	oldfence.in
Имя выходного файла:	oldfence.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Сому Тойеру необходимо покрасить старый забор, состоящий из n досок, в белый цвет, иначе он не сможет посидеть за компьютером. У Сома Тойера есть несколько друзей, которые горят желанием помочь Сому. Друзья собрались вместе и распределили, кто какой участок забора будет красить. После покраски Сом заметил, что на некоторых участках забора находится несколько слоев краски, а некоторые доски так и остались непокрашенными.

Сом Тойер знает, кто из его друзей красил какой участок. Теперь ему нужно узнать, сколько краски ушло на различные участки этого забора. Сам он не может найти ответ. Помогите ему.

Формат входного файла

Первая строка файла содержит длину забора n (1 ≤ n ≤ 1000000), количество друзей m (1 ≤ m ≤ 200000), и количество участков k (0 ≤ k ≤ 200000), на которых Сом Тойер хочет узнать количество покрасок. Каждая доска забора нумеруется от 1 до n, друзья Сома Тойера пронумерованы числами от 1 до m. В следующих m строках задаются участки, которые красил каждый из друзей Сома. Участок задается двумя числами b_i и e_i – номерами досок (1 ≤ b_i ≤ e_i ≤ n) и количество слоев краски d_i, которые нанес друг на каждую из досок (0 ≤ d_i ≤ 1000000). Следующие k строк содержат описание участков, для которых Сом хочет узнать количество потраченной краски (сумма количества слоев на каждой доске). Участок задается двумя числами c_i и d_i – номера досок.

Формат выходного файла

Выходной файл должен содержать k строк, содержащих ответ на каждый вопрос Сома (количество краски потраченной на каждом отрезке).

Пример:

oldfence.in	oldfence.out
8 4 5 1 3 2 4 6 3 6 8 4 3 5 1 1 3 5 8 4 4 3 4 1 1	7 19 4 7 2

Источник: Командное школьное первенство Республики Карелия по программированию, октябрь 2008.

Обсудить       Отправить решение



Версия для печати