Subarray Sum Constraints

题目描述

你的任务是构造一个由 n 个整数组成的数组 $x_1,x_2,\dots,x_n$。 该数组必须满足 m 个形如 $(l,r,s)$ 的约束：和 $x_l + x_{l+1} + \dots + x_r$ 必须等于 $s$。

输入格式

第一行有两个整数 n 和 m：数组的长度和约束的个数。 接下来的 m 行每行有三个整数 l、r 和 s：约束的描述。

输出格式

如果存在解，第一行输出 YES。 在第二行，输出 n 个整数 $x_1, x_2,\dots, x_n$：数组的内容。数组的所有元素必须满足 $-10^{15} \le x_i \le 10^{15}$ 且数组必须满足所有给定的约束。你可以输出任意一个有效解。 如果不存在解，则仅输出 NO。

5 3
1 3 3
3 5 3
4 4 -1

YES
0 2 1 -1 3

提示

$1 \le n \le 5000$ $0 \le m \le 2 \cdot 10^5$ $1 \le l \le r \le n$ $-10^9 \le s \le 10^9$

标签: CSES3294|附加题1

来源

CSES3294|附加题1