P3588 [POI2015]PUS

    • 246通过
    • 758提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 拓扑排序 线段树 记忆化搜索 POI 2015 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一个长度为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 \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: 复制
    5 2 2
    2 7
    5 3
    1 4 2 2 3
    4 5 1 4
    输出样例#1: 复制
    TAK
    6 7 1000000000 6 3
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。