#4383. [POI2015] Pustynia

[POI2015] Pustynia

题目描述

给定一个长度为n的正整数序列a,每个数都在1到10^9范围内,告诉你其中s个数,并给出m条信息,每条信息包含三个数l,r,k以及接下来k个正整数,表示a[l],a[l+1],...,a[r-1],a[r]里这k个数中的任意一个都比任意一个剩下的r-l+1-k个数大(严格大于,即没有等号)。 请任意构造出一组满足条件的方案,或者判断无解。

输入格式

第一行包含三个正整数n,s,m(1<=s<=n<=100000,1<=m<=200000)。 接下来s行,每行包含两个正整数p[i],di,表示已知a[p[i]]=d[i],保证p[i]递增。 接下来m行,每行一开始为三个正整数l[i],r[i],ki,接下来k[i]个正整数x[1],x[2],...,xk[i],表示这k[i]个数中的任意一个都比任意一个剩下的r[i]-l[i]+1-k[i]个数大。Σk <= 300,000

输出格式

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

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

TAK
6 7 1000000000 6 3

提示

没有写明提示

题目来源

鸣谢Claris