AT_agc079_b.Range Record

NOI/NOI+/CTSC

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given integers N,MN,M and MM triples of integers (Li,Ri,Ci)(L_i,R_i,C_i). Here, 1≤Li<Ri≤N1 \leq L_i < R_i \leq N, and the pairs (Li,Ri)(L_i,R_i) are pairwise distinct.

Determine whether there exists a permutation P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N) of (1,2,…,N)(1,2,\ldots,N) that satisfies all of the following MM conditions. If one exists, find one such permutation.

  • The ii-th condition: the number of integers jj such that Li≤j≤RiL_i \leq j \leq R_i and max⁡(PLi,PLi+1,…,Pj)=Pj\max(P_{L_i},P_{L_i+1},\ldots,P_j)=P_j is exactly CiC_i.

You are given TT test cases; solve each of them.

给你整数 N,MN,M 以及 MM 个整数三元组 (Li,Ri,Ci)(L_i,R_i,C_i)。其中,满足 1≤Li<Ri≤N1 \leq L_i < R_i \leq N,且所有二元组 (Li,Ri)(L_i,R_i) 互不相同。

判断是否存在一个 (1,2,…,N)(1,2,\ldots,N) 的排列 P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N),使得以下 MM 个条件全部成立。若存在,输出任意一个满足条件的排列。

  • 第 ii 个条件:在下标区间 j∈[Li,Ri]j \in [L_i, R_i] 中,满足 max⁡(PLi,PLi+1,…,Pj)=Pj\max(P_{L_i},P_{L_i+1},\ldots,P_j)=P_j 的整数 jj 的个数恰好为 CiC_i。

你将得到 TT 组测试数据;请分别求解每组数据。

输入格式

The input is given from Standard Input in the following format:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

Each test case is given in the following format:

NN MM
L1L_1 R1R_1 C1C_1
L2L_2 R2R_2 C2C_2
⋮\vdots
LML_M RMR_M CMC_M

输入从标准输入中按以下格式给出:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

每个测试用例按以下格式给出:

NN MM
L1L_1 R1R_1 C1C_1
L2L_2 R2R_2 C2C_2
⋮\vdots
LML_M RMR_M CMC_M

输出格式

For each test case, if a permutation satisfying the conditions exists, output Yes on the first line and the elements of such a permutation PP, 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,在第二行输出该排列 PP 的各元素(以空格分隔)。若存在多个满足条件的排列,则输出任意一个均可。

如果不存在这样的排列,则在单独一行输出 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)P=(2,4,1,3) satisfies the conditions. The integers jj counted in each condition are j=1,2j=1,2 for the interval [1,4][1,4], j=2j=2 for the interval [2,4][2,4], and j=3,4j=3,4 for the interval [3,4][3,4].

In the second test case, the first two conditions require P1<P2<P3P_1 \lt P_2 \lt P_3. Then, the number of integers jj counted for the interval [1,3][1,3] is 33, which violates the third condition, so no such permutation exists.

Constraints

  • 1≤T≤1250001 \leq T \leq 125000
  • 2≤N≤1002 \leq N \leq 100
  • 1≤M≤N(N−1)21 \leq M \leq \dfrac{N(N-1)}{2}
  • 1≤Li<Ri≤N1 \leq L_i \lt R_i \leq N (1≤i≤M)(1 \leq i \leq M)
  • (Li,Ri)≠(Lj,Rj)(L_i,R_i) \neq (L_j,R_j) (1≤i<j≤M)(1 \leq i \lt j \leq M)
  • 1≤Ci≤Ri−Li+11 \leq C_i \leq R_i-L_i+1 (1≤i≤M)(1 \leq i \leq M)
  • The sum of N3N^3 over all test cases in a single input is at most 10610^6.
  • All input values are integers.

样例 1 解释:
在第一个测试用例中,例如,排列 P=(2,4,1,3)P=(2,4,1,3) 满足所有条件。各区间条件下被计数的整数 jj 分别为:对区间 [1,4][1,4],满足条件的 jj 为 j=1,2j=1,2;对区间 [2,4][2,4],满足条件的 jj 为 j=2j=2;对区间 [3,4][3,4],满足条件的 jj 为 j=3,4j=3,4。

在第二个测试用例中,前两个条件要求 P1<P2<P3P_1 \lt P_2 \lt P_3。此时,对区间 [1,3][1,3] 计数得到的整数 jj 的个数为 33,违反了第三个条件,因此不存在满足所有条件的排列。

约束条件

  • 1≤T≤1250001 \leq T \leq 125000
  • 2≤N≤1002 \leq N \leq 100
  • 1≤M≤N(N−1)21 \leq M \leq \dfrac{N(N-1)}{2}
  • 1≤Li<Ri≤N1 \leq L_i \lt R_i \leq N (1≤i≤M)(1 \leq i \leq M)
  • (Li,Ri)≠(Lj,Rj)(L_i,R_i) \neq (L_j,R_j) (1≤i<j≤M)(1 \leq i \lt j \leq M)
  • 1≤Ci≤Ri−Li+11 \leq C_i \leq R_i-L_i+1 (1≤i≤M)(1 \leq i \leq M)
  • 所有测试用例的 N3N^3 之和不超过 10610^6。
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页