32967번 - 스파이 서브태스크

한국정보기술진흥원에는 $N$명의 스파이가 있습니다. $i$번 스파이는 $S_i$시 정각에 출근해서 $E_i$시 정각에 퇴근하며, 보안 등급 $D_i$를 갖습니다.

한 스파이는 출근해서 퇴근하기 전까지 자신이 알고 있거나, 알게 된 정보를 출근해 있는 다른 스파이에게 직접 전달할 수 있습니다. 한 스파이의 퇴근 시간이 다른 스파이의 출근 시간과 같다면, 두 스파이는 서로 정보를 직접 전달할 수 없습니다.

$i$번 스파이는 $j$번 스파이에게 최대한 은밀하게 정보를 전달하려 합니다.

$i$번 스파이가 출근하면서 가져온 정보를 스파이들이 서로 잘 전달하여 $j$번 스파이에게 정보가 전달되는 각 경우를 시나리오라고 합시다. 각 시나리오의 **안전도**는 전달 중에 정보를 알게 된 모든 스파이의 보안 등급의 최솟값입니다.

$d(i,j)$는 가능한 모든 시나리오의 안전도의 최댓값으로 정의됩니다. 만약 가능한 시나리오가 없다면 $d(i, j)=0$입니다.

$i\neq j$인 모든 $i$, $j$에 대해 $d(i, j)$의 합을 구해주세요!

첫 번째 줄에 스파이의 수 $N$이 주어집니다,

이후 $N$개의 줄에 걸쳐 스파이들의 정보 $S_i, E_i, D_i$가 공백을 사이에 두고 주어집니다.

첫 번째 줄에 $i\neq j$인 모든 $i$, $j$에 대해 $d(i, j)$의 합을 구해 출력합니다.

• $2 \le N \le 200\, 000$
• $1\le S_i < E_i\le 10^9$
• $1\le D_i \le 10^7$

예제 1의 경우, 모든 스파이의 보안 등급이 $1$이므로 $d(i, j)$는 스파이 $i$가 스파이 $j$에게 정보를 전달할 수 있는 경우 $1$, 아닌 경우 $0$이 됩니다. 따라서 모든 $i, j$ ($i \ne j$)에 대한 $d(i, j)$의 값은 다음과 같습니다.

• $i=1, j=2$: 두 스파이가 직접적으로 정보를 전달하면 되므로 $d(1, 2)=1$입니다.
• $i=1, j=3$: $1$번 스파이가 $2$번 스파이에게 정보를 전달하고, $2$번 스파이가 $3$번 스파이에게 정보를 전달하면 됩니다. 따라서 $d(1,3)=1$입니다.
• $i=2, j=1$: 두 ���파이가 직접적으로 정보를 전달하면 되므로 $d(2, 1)=1$입니다.
• $i=2, j=3$: 두 스파이가 직접적으로 정보를 전달하면 되므로 $d(2, 3)=1$입니다.
• $i=3, j=1$: $3$번 스파이의 출근 시간이 $1$번 스파이의 퇴근 시간 이후이므로 정보를 전달할 방법이 없습니다. 따라서 $d(3, 1)=0$입니다.
• $i=3, j=2$: 두 스파이가 직접적으로 정보를 전달하면 되므로 $d(3, 2)=1$입니다.

따라서 $1+1+1+1+0+1=5$를 출력해야 합니다.