e-olymp
Соревнования

Segment Tree - Multiple Update

Городской горизонт

Фермер Джон приехал со своими коровами в город! Во время захода солнца коровы смотрят на городской горизонт и наблюдают красивые силуэты, образованные прямоугольными зданиями.

Весь горизонт представлен числовой прямой с n (1n40000) зданиями. Силуэт i-го здания распростерся вдоль горизонта между точками ai и bi (1ai < bi109) и имеет высоту hi (1hi109). Определите площадь в квадратных единицах общего силуэта, образованного всеми n зданиями.

Входные данные

Первая строка содержит целое число n. Каждая из следующих n строк описывает здание i тремя целыми числами: ai, bi и hi.

Выходные данные

Выведите общую площадь городского силуэта в квадратных единицах, образованного всеми n зданиями.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4
2 5 1
9 10 4
6 8 2
4 6 3
Выходные данные #1
16
Источник 2007 USACO US Open, Silver Division