Вычисление сложности программы
Первоисточник: Цикл Интернет-олимпиад для школьников
URL первоисточника: http://ctddev.ifmo.ru/school/io/archive.html
Задачу добавил: elena
Успешно сдано решений: 0
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Аня решила стать чемпионкой мира по программированию. Для этого ей, кроме всего прочего, потребовалось научиться вычислять время работы программ. Во многих программах основное время работы занимают вложенные циклы. Поэтому Аня хочет научиться узнавать, сколько операций будет выполнено внутри последовательности вложенных циклов.
Пока Аня еще только учится, поэтому все программы выглядят как последовательность вложенных циклов, причем все циклы выполняются от некоторого числа или переменной до некоторого другого числа. Ей требуется найти, сколько раз будет выполнена операция внутри самого
вложенного цикла. Для этого она создала счетчик, проинициализировала его нулем, и увеличивает его на единицу каждый раз, входя в самый вложенный цикл. Заметьте, что Аня пока не знает, что в качестве верхней границы в цикле может служить переменная. В качестве нижней границы может выступать как переменная, так и фиксированное значение. Если в каком-то цикле левая граница больше, чем правая, то цикл не будет выполняться
вообще.
Так как программы у Ани иногда работают очень долго, то она попросила своего друга узнать ответ, когда же и он не смог этого посчитать, она попросила об этом вас. Помогите ей.
Напишите программу, которая находит, какое значение будет в счетчике в конце работы Аниной программы, если счетчик хранился в переменной целого 32-битного беззнакового типа.
Формат входного файла
В первой строке находится число 1<= N <= 3 000 - количество циклов. Далее в N строках написано по два целых числа в каждой. В i+1-й строке входного файла записаны левая и правая граница i-го цикла: Li и Ri (1-i<= Li <=3000, 0<= Ri<=3 000). При этом если Li < 0, то это обозначает, что цикл начинается со значения переменной (-Li)-го цикла, в противном случае цикл начинается со значения Li.
Формат выходного файла
Выведите значение, которое будет в счетчике в конце работы программы.
Пример входного файла
2
1 100
-1 100
Пример выходного файла
5050
Пример входного файла
2
4 6
-1 3
Пример выходного файла
0
Пример входного файла
4
1 256
1 256
1 256
1 256
Пример выходного файла
0
Пример входного файла
4
1 1000
1 1000
1 1000
1 1000
Пример выходного файла
3567587328