AdditionalFile4968.zip

P3588 [POI 2015 R2] 沙漠 Desert

题目描述

给定一个长度为 $n$ 的正整数序列 $a$，每个数都在 $1$ 到 $10^9$ 范围内，告诉你其中 $s$ 个数，并给出 $m$ 条信息，每条信息包含三个数 $l,r,k$ 以及接下来 $k$ 个正整数，表示 $a_l, a_{l+1}, \ldots, a_{r-1}, a_r$ 里这 $k$ 个数中的任意一个都比任意一个剩下的 $r-l+1-k$ 个数大（严格大于，即没有等号）。

请任意构造出一组满足条件的方案，或者判断无解。

输入格式

第一行包含三个正整数 $n,s,m$（$1 \leq s \leq n \leq 10^5$，$1 \leq m \leq 2 \times 10^5$）。接下来 $s$ 行，每行包含两个正整数 $p_i,d_i$,表示已知 $a_{p_i}=d_i$，保证 $p_i$ 递增。

接下来 $m$ 行,每行一开始为三个正整数 $l_i,r_i,k_i$（$1 \leq l_i < r_i \leq n$，$1 \leq k_i \leq r_i-l_i$），接下来 $k_i$ 个正整数 $x_1..x_2...x_{k_i}$（$l_i \leq x_1 < x_2 < ... < x_{k_i} \leq r_i$），表示这 $k_i$ 个数中的任意一个都比任意一个剩下的 $r_i-l_i+1-k_i$ 个数大。（$\sum k \leq 3 \times 10^5$）

输出格式

若无解，则输出 NIE。否则第一行输出 TAK，第二行输出 $n$ 个正整数，依次输出序列 $a$ 中每个数。

输入输出样例 #1

输入 #1

5 2 2
2 7
5 3
1 4 2 2 3
4 5 1 4

输出 #1

TAK
6 7 1000000000 6 3

输入输出样例 #2

输入 #2

3 2 1
2 3
3 5
1 3 1 2

输出 #2

NIE

输入输出样例 #3

输入 #3

2 1 1
1 1000000000
1 2 1 2

输出 #3

NIE

说明/提示

原题名称：Pustynia。

本题另外提供两组额外样例，可以在附件中下载。

#4968. 「POI2015 R2」沙漠 Desert

标签: 传统 | 时间限制: 1500 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXII Olimpiada Informatyczna — II etap Pustynia

从 Bajtadu 到 Bajtary 的道路穿越字节城大沙漠的茫茫沙海，旅途艰辛，沿途仅有 $s$ 口水井。字节城国王深知交通命脉对经济至关重要，决定在路上增挖水井。Bajtadu 到 Bajtary 的距离为 $n+1$ 英里，每隔整数英里的点可存在或新建水井。地下水越深，挖井成本越高，施工难度越大。

国王委托宫廷地质学家 Bajtazar 调查此事。Bajtazar 使用卫星网络获取了 $m$ 次测量数据，但卫星仅提供相对深度信息：每次测量针对一段连续路段，指明某些点水深严格大于其他点。此外，已知每个点的水深为 $1$ 到 $10^9$ 米的整数。请你帮助 Bajtazar，确定每个点的可能水深，或判断卫星数据是否矛盾。

输入格式

第一行包含三个整数 $n, s, m$ $(1 \leq s \leq n \leq 100000, 1 \leq m \leq 200000)$，分别表示两城间距离（不含起点）、水井数和卫星测量次数。

接下来的 $s$ 行描述水井，第 $i$ 行包含两个整数 $p_i, d_i$ $(1 \leq p_i \leq n, 1 \leq d_i \leq 10^9)$，表示第 $i$ 口水井距巴伊塔杜 $p_i$ 英里，水深 $d_i$ 米。水井按 $p_i$ 升序排列。

接下来的 $m$ 行描述卫星测量，第 $i$ 行包含三个整数 $l_i, r_i, k_i$ $(1 \leq l_i < r_i \leq n, 1 \leq k_i \leq r_i - l_i)$，后接 $k_i$ 个整数 $x_1, x_2, \ldots, x_{k_i}$ $(l_i \leq x_1 < x_2 < \ldots < x_{k_i} \leq r_i)$，表示在路段 $l_i$ 到 $r_i$（含端点）内，点 $x_1, \ldots, x_{k_i}$ 的水深严格大于其他点。所有 $k_i$ 的总和不超过 $200000$。

输出格式

若不存在符合测量数据的深度方案，输出一行一个字符串 NIE。

否则，输出两行：第一行输出 TAK，第二行包含 $n$ 个 $1$ 到 $10^9$ 之间的整数，表示从巴伊塔杜开始各点的水深。若有多种方案，输出任意一种。

样例 1

输入

5 2 2
2 7
5 3
1 4 2 2 3
4 5 1 4

输出

TAK
6 7 1000000000 6 3

样例 2

输入

3 2 1
2 3
3 5
1 3 1 2

输出

NIE

样例 3

输入

2 1 1
1 1000000000
1 2 1 2

输出

NIE

附加样例

1. $n=100000$，测量表明点 $i$ 的水深大于所有前序点（$i=2, \ldots, n$）；
2. $n=100000$，一次测量表明偶数编号点水深大于奇数编号点。

数据范围与提示

对于 $60\%$ 的数据，$n, m \leq 1000$。
对于 $30\%$ 的数据，所有 $k_i$ 的总和不超过 $1000$。