#P11764. 「KFCOI Round #1」生成序列

    ID: 12986 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>洛谷原创Special JudgeO2优化构造洛谷比赛

「KFCOI Round #1」生成序列

题目背景

题目描述

你需要生成一个长度为 nn 的非负整数序列 aa

aa 满足 mm 条限制,第 ii 条限制形如:

  • 若将 axia_{x_i} 修改为 yiy_i,则序列中恰好有 kik_i 个区间满足修改前后,其区间和的变化量不超过 pip_i

各个限制间独立,即修改操作没有真的执行。

为了防止序列中的数过大,如果存在 ai>2×109a_i>2\times 10^9,则认为序列 aa 不满足限制。

若有多个满足条件的序列,输出任意一个即可。若无解,输出 -1

输入格式

本题输入均为正整数。

第一行一个数 TT

对于每组数据:

第一行两个数 n,mn,m

接下来 mm 行,每行四个数 xi,yi,ki,pix_i,y_i,k_i,p_i

输出格式

本题使用 SPJ

每组数据一行。

若有解,输出 nn 个非负整数,第 ii 个数代表 aia_i

若无解,输出 -1

2
4 4
4 1 6 1
3 20 10 12
2 3 4 4
4 9 10 10
3 2
1 2 6 0
1 3 6 0
6 20 18 4
-1

提示

样例解释

对于第一组数据:

a1=6a_1=6a2=20a_2=20a3=18a_3=18a4=4a_4=4

若将 a4a_4 改为 11,则有 66 个区间的区间和变化量不超过 11,分别为:

[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]

若将 a3a_3 改为 2020,则所有区间的区间和变化量均不超过 1212

若将 a2a_2 改为 33,则有 44 个区间的区间和变化量不超过 44,分别为:

[1,1],[3,3],[3,4],[4,4]

若将 a4a_4 改为 99,则所有区间的区间和变化量均不超过 1010

可能存在其他解,输出任意一个即可。

对于第二组数据,可以证明没有符合条件的序列满足限制。


数据范围

本题采用捆绑测试

  • Subtask 1(10 points):1n101 \le n \le 101m101 \le m \le 101yi101 \le y_i \le 101pi101 \le p_i\le 10
  • Subtask 2(10 points):m=1m=1
  • Subtask 3(10 points):ki=n(n+1)2k_i=\frac{n(n+1)}{2}
  • Subtask 4(20 points):1n1041 \le n \le 10 ^ 41m1041 \le m \le 10 ^ 41yi1041 \le y_i \le 10 ^41pi1041 \le p_i\le 10^4
  • Subtask 5(50 points):无特殊限制。

对于所有测试数据,1n1051 \le n\le 10^51m1051\le m\le 10^51T101 \le T\le 101xin1\le x_i\le n1kin(n+1)21 \le k_i\le \frac{n(n+1)}{2}1yi1091 \le y_i \le 10 ^ 91pi1091 \le p_i\le 10^9