문제풀이
- r에 대하여 조건을 만족하는 l의 범위를 구한다. (L[r] = 조건을 만족하는 최소 l)
- N개의 구간에서 r일 때 l+1부터 가능하다.
- r의 최소 l은 r-1의 최소 l보다 크거나 같아야한다.
주의사항
소요시간
20분
package AtCoder.ABC.ABC377.D
fun main() {
val (N, M) = readln().trim().split(" ").map(String::toInt)
val L = IntArray(M + 1) { 1 }
repeat(N) {
val (l, r) = readln().trim().split(" ").map(String::toInt)
L[r] = maxOf(L[r], l + 1)
}
for (r in 1..M) {
L[r] = maxOf(L[r], L[r - 1])
}
var result = 0L
for (r in 1..M) {
result += maxOf(0, r - L[r] + 1)
}
println(result)
}