AT_agc079_b.Range Record
NOI/NOI+/CTSC
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given integers N,M and M triples of integers (Li,Ri,Ci). Here, 1≤Li<Ri≤N, and the pairs (Li,Ri) are pairwise distinct.
Determine whether there exists a permutation P=(P1,P2,…,PN) of (1,2,…,N) that satisfies all of the following M conditions. If one exists, find one such permutation.
- The i-th condition: the number of integers j such that Li≤j≤Ri and max(PLi,PLi+1,…,Pj)=Pj is exactly Ci.
You are given T test cases; solve each of them.
给你整数 N,M 以及 M 个整数三元组 (Li,Ri,Ci)。其中,满足 1≤Li<Ri≤N,且所有二元组 (Li,Ri) 互不相同。
判断是否存在一个 (1,2,…,N) 的排列 P=(P1,P2,…,PN),使得以下 M 个条件全部成立。若存在,输出任意一个满足条件的排列。
- 第 i 个条件:在下标区间 j∈[Li,Ri] 中,满足 max(PLi,PLi+1,…,Pj)=Pj 的整数 j 的个数恰好为 Ci。
你将得到 T 组测试数据;请分别求解每组数据。
输入格式
The input is given from Standard Input in the following format:
T
case1
case2
⋮
caseT
Each test case is given in the following format:
N M
L1 R1 C1
L2 R2 C2
⋮
LM RM CM
输入从标准输入中按以下格式给出:
T
case1
case2
⋮
caseT
每个测试用例按以下格式给出:
N M
L1 R1 C1
L2 R2 C2
⋮
LM RM CM
输出格式
For each test case, if a permutation satisfying the conditions exists, output Yes on the first line and the elements of such a permutation P, separated by spaces, on the second line. If there are multiple such permutations, any of them will be accepted.
If no such permutation exists, output No on a single line.
对于每个测试用例,如果存在满足条件的排列,则在第一行输出 Yes,在第二行输出该排列 P 的各元素(以空格分隔)。若存在多个满足条件的排列,则输出任意一个均可。
如果不存在这样的排列,则在单独一行输出 No。
输入输出样例
输入#1
8 4 3 1 4 2 2 4 1 3 4 2 3 3 1 2 2 2 3 2 1 3 2 2 1 1 2 1 2 1 1 2 2 6 5 1 6 3 2 5 3 3 6 2 4 6 1 5 6 2 5 10 1 2 2 1 3 2 1 4 2 1 5 2 2 3 1 2 4 1 2 5 1 3 4 2 3 5 2 4 5 1 3 2 1 3 3 2 3 1 3 2 1 2 1 1 3 2
输出#1
Yes 2 4 1 3 No Yes 2 1 Yes 1 2 Yes 2 1 4 6 3 5 Yes 2 5 1 4 3 No Yes 2 1 3
说明/提示
Sample 1 Explanation:
In the first test case, for example, P=(2,4,1,3) satisfies the conditions. The integers j counted in each condition are j=1,2 for the interval [1,4], j=2 for the interval [2,4], and j=3,4 for the interval [3,4].
In the second test case, the first two conditions require P1<P2<P3. Then, the number of integers j counted for the interval [1,3] is 3, which violates the third condition, so no such permutation exists.
Constraints
- 1≤T≤125000
- 2≤N≤100
- 1≤M≤2N(N−1)
- 1≤Li<Ri≤N (1≤i≤M)
- (Li,Ri)=(Lj,Rj) (1≤i<j≤M)
- 1≤Ci≤Ri−Li+1 (1≤i≤M)
- The sum of N3 over all test cases in a single input is at most 106.
- All input values are integers.
样例 1 解释:
在第一个测试用例中,例如,排列 P=(2,4,1,3) 满足所有条件。各区间条件下被计数的整数 j 分别为:对区间 [1,4],满足条件的 j 为 j=1,2;对区间 [2,4],满足条件的 j 为 j=2;对区间 [3,4],满足条件的 j 为 j=3,4。
在第二个测试用例中,前两个条件要求 P1<P2<P3。此时,对区间 [1,3] 计数得到的整数 j 的个数为 3,违反了第三个条件,因此不存在满足所有条件的排列。
约束条件
- 1≤T≤125000
- 2≤N≤100
- 1≤M≤2N(N−1)
- 1≤Li<Ri≤N (1≤i≤M)
- (Li,Ri)=(Lj,Rj) (1≤i<j≤M)
- 1≤Ci≤Ri−Li+1 (1≤i≤M)
- 所有测试用例的 N3 之和不超过 106。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?