문제
"농부 창호는 자신의 소들을 데리고 한적한 도시에서 조금은 시끄러운 도시로 여행을 떠났다.
험난한 여정을 끝내고 도시에 도착했을 때 지평선에 펼쳐진 일출과
직사각형 형태의 빌딩의 실루엣들이 소들을 환영하고 있었다."
지평선위에는 N개의 빌딩이 서 있으며 길이는 유한하다고 하자.
각 빌딩의 실루엣은 지평선 바로 위에 위치 해 있으며
지평선 내에서의 정수의 가장 왼쪽과 오른쪽의 위치를 가지고 있으며 1이상의 높이를 가지고 있다.
빌딩끼리는 서로 겹쳐서 위치 할 수 있으며 높이가 높은 빌딩이 다른 빌딩을 가려서 나타날 수 있다.
이에 대한 정보가 주어졌을 때 소들에게 보이는 빌딩의 넓이를 구하는 프로그램을 작성하라.
입력
첫 번째 줄에는 빌딩의 개수 N(1≤N≤40,000)이 입력된다.
두 번째 줄부터 N+1 번째 줄은 빌딩의 실루엣에 대한 정보가 입력된다.
i+1번째 줄은 i번째 빌딩의 정보가 입력되며 공백을 사이에 두고 Ai, Bi (1 ≤ Ai＜ Bi ≤ 1,000,000,000), Hi (1 ≤ Hi ≤ 1,000,000,000)가 입력되는데 이는 각각 빌딩의 맨 왼쪽 위치 맨 오른쪽 위치 그리고 높이를 뜻한다.
또한 앞에서 언급 하였듯 빌딩의 실루엣은 직사각형의 형태로 이루어진다.
출력
입력 받은 도시의 정보에 대해 보이는 실루엣의 넓이를 출력하라.
예제1
입력
4
2 5 1
9 10 4
6 8 2
4 6 3
출력
16
위의 예제를 그림으로 표현하면 아래와 같다.
출처
USACO 2007 Open Silver, poj 3277