문제
정올시는 길이가 D인 수평선 위에 N개의 빌딩이 놓여 있는 구조로 되어있다.
정올시의 시장은 도시에 가로등을 설치하기보다, 일부 빌딩을 등대로 만들기를 택했다.
등대가 된 빌딩은 옥상에서 모든 방향으로 빛을 비춘다. 하지만 당연하게도, 다른 빌딩에 가로막혀 빛이 닿지 않는 곳이 있을 수 있다.
정올시의 땅 중 빛이 닿는 땅의 크기는 얼마일까?
빌딩의 너비는 무시할 수 있을만큼 작다.
아래 그림은 예제 2번이다. 굵게 칠해진 x축이 빛이 닿지 않는 곳이다.
<제한조건>
1 ≤ N ≤ 300,000
1 ≤ D ≤ 1,000,000,000
0 ≤ Xi ≤ D
1 ≤ Hi ≤ 1,000,000,000
입력
첫번째 줄에 두 정수 N과 D가 띄어쓰기로 구분되어 입력된다.
두번째 줄부터 N개의 줄 동안 각 줄에 세 정수 Li, Xi, Hi가 띄어쓰기로 구분되어 입력된다.
Li가 1일 경우 i번 빌딩은 등대가 된 빌딩이며, 0일 경우 일반 빌딩이다.
Xi는 i번 빌딩이 정올시의 왼쪽 끝으로부터 떨어져 있는 거리다.
Hi는 i번 빌딩의 높이다.
빌딩의 위치는 모두 다르며, Xi가 증가하는 순으로 주어진다.
출력
첫 줄에 빛이 닿는 땅의 길이를 출력한다.
소숫점은 반올림하여 정수로 출력한다.
round() 함수와 %.0f를 이용한 출력의 결과는 다를 수 있다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 30점 | N ≤ 1,000 |
| #2 | 70점 | 추가적인 제한이 없다. |
예제 #1
3 10
1 2 6
0 4 3
0 8 2
6
예제 #2
5 15
0 4 3
1 5 5
1 6 6
0 9 2
0 10 3
9
로그인해야 코드를 작성할 수 있어요.