← 返回题目列表

AtCoder · awc0045_c

C. 浇水职责

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥是学校园艺委员会的成员。校园里,有 N 花槽从东向西呈直线排列,编号为Planter 1,播种机 2, \ldots,播种机 N 从西到东。开始浇水前,每个花盆的水量为 0 升。

从今天开始,高桥被分配浇水任务 Q 天。当天 i (1 \leq i \leq Q),他从 Planter 给每个花盆浇水 L_i 到播种机 R_i (含)与 C_i 升水。

毕竟 Q 浇水天数已完成,求每个播种机的总浇水量 1,播种机 2, \ldots,播种机 N.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N
  • 1 \leq C_i \leq 10^4
  • 所有输入值均为整数

输入

N Q
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_Q R_Q C_Q
  • 第一行包含花盆数量 N 和浇水天数 Q,用空格分隔。
  • 的 (i + 1)第行 (1 \leq i \leq Q) 包含起始播种机编号 L_i,结束种植者编号 R_i和水量 C_i 当天发给每个种植者 i,用空格分隔。

输出

打印 N 单行上用空格分隔的整数。这 j- 第一个整数 (1 \leq j \leq N) 代表给予 Planter 的水总量(以升为单位) j。即从 Planter 打印总金额 1 通过播种机 N 按顺序。


示例输入 1

5 3
1 3 2
2 4 3
4 5 1

示例输出 1

2 5 5 4 1

示例输入 2

10 5
1 10 1
3 7 2
5 5 10
1 1 5
8 10 3

示例输出 2

6 1 3 3 13 3 3 4 4 4

示例输入 3

20 8
1 20 100
5 15 50
1 5 30
16 20 30
10 10 500
3 8 25
12 18 40
7 14 15

示例输出 3

130 130 155 155 205 175 190 190 165 665 165 205 205 205 190 170 170 170 130 130