#P5658. 城市地平线

城市地平线

题目描述

农夫约翰带着他的奶牛去城里旅行了!日落时,奶牛凝视着城市的地平线,观察着矩形建筑形成的美丽轮廓。

整个地平线由一条数字线表示,其中有N{N(}1<=N<=40000{1<=N<=40000)}座建筑物.建筑物i{i}的轮廓有一个基座,沿地平线跨越位置Ai{A_i}Bi{B_i(}1<=Ai<Bi<=100000000{1<=A_i<B_i<=100000000)},高度hi{h_i(}1<=hi<=100000000{1<=h_i<=100000000)}

以平方单位确定由所有n{n}栋建筑形成的总轮廓的面积。 N{N}个矩形块,交求面积并.

输入格式

1{1}行:单个整数:N{N}

2...N+1{2...N+1}行:输入行i+1{i+1}用三个空格分隔的整数描述建筑物i{i:}Ai{A_ i}Bi{B_ i}Hi{H_ i}

输出格式

1{1}行:所有N{N}栋建筑形成的轮廓的总面积(以平方为单位)

样例

输入样例

4
2 5 1
9 10 4
6 8 2
4 6 3

输出样例

16

提示

输出详细信息:

第一栋建筑与第四栋建筑重叠,面积为1{1}平方单位,所以总面积只有3×1+1×4+2×2+2×31=16{3\times 1+1\times 4+2\times 2+2\times 3-1=16}