D - Deforestation
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 本の竹があり、1 から N までの番号がつけられています。 時刻 0 において、すべての竹の高さは 0 です。 それぞれの竹は、時刻が 1 経過するごとに高さが 1 増えます。
ナオさんが竹を伐採するイベントが M 回予定されています。 i 番目のイベントは時刻 T_i に行われ、このイベントでは番号が L_i 以上 R_i 以下の竹をすべて伐採します。 ナオさんが高さ x の竹を伐採するとき、彼女は x 点を得ます。 また、伐採された竹は高さが 0 になりますが、その竹はこれ以降も伸び続けます。
M 回のイベントでナオさんが得る得点の総和を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq T_1 < T_2 < \cdots < T_M \leq 10^9
- 1 \leq L_i \leq R_i \leq N
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M T_1 L_1 R_1 T_2 L_2 R_2 \vdots T_M L_M R_M
出力
M 回のイベントでナオさんが得る得点の総和を出力せよ。
入力例 1
4 2 2 1 2 5 2 3
出力例 1
12
1 番目のイベントが行われる時刻 2 では、竹の高さはそれぞれ 2,2,2,2 です。 竹 1 と 2 を伐採すると、竹の高さはそれぞれ 0,0,2,2 になります。
2 番目のイベントが行われる時刻 5 では、竹の高さはそれぞれ 3,3,5,5 です。 竹 2 と 3 を伐採すると、竹の高さはそれぞれ 3,0,0,5 になります。
2 回のイベントで伐採した竹の高さはそれぞれ 2,2,3,5 なので、その総和である 12 が答えです。
入力例 2
10 5 8 1 4 11 6 7 20 1 1 31 9 9 36 1 1
出力例 2
113
入力例 3
10 10 76724435 3 4 118633459 1 2 288866156 6 9 470883673 6 10 521545097 2 4 827053186 1 1 856004743 2 4 873331881 1 1 909855542 6 10 916091889 8 9
出力例 3
8003096514