#P11820. [PA 2015] 健身房 / Siłownia

    ID: 13070 远端评测题 8100ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>贪心2015线段树数据结构Special JudgeO2优化PA(波兰)

[PA 2015] 健身房 / Siłownia

题目背景

译自 PA 2015 R5.

题目描述

健身房里有 kk 个器材。

nn 个人预约了健身。第 ii 个人预约给定了 li,ri,pil_i,r_i,p_i,意思是要分配给他 li,li+1,,ril_i,l_{i}+1,\cdots,r_i 中的一个(记为 xx),他在第 xx 个小时中用器材 pip_i 健身。

同一时间不能有两个人用同一个健身器材。此外,老板还希望让健身房里没人的时刻尽量多,这样可以节约电费。

构造一组最优解。

输入格式

第一行,两个正整数 n,kn,k

接下来 nn 行,第 ii 行三个正整数 li,ri,pil_i,r_i,p_i

输出格式

如果无解,输出一行一个 NIE\texttt{NIE}

否则输出 (n+1)(n+1) 行:第一行一个整数,表示在最优策略下,有多少个时刻健身房至少有一个人。接下来 nn 行,第 ii 行的整数表示第 ii 个人分配的 xx

4 2
1 3 1
1 1 1
1 3 2
3 3 2
2
3
1
1
3
3 1
1 2 1
1 2 1
1 2 1
NIE

提示

  • 1n1061\le n\le 10^6
  • 1k1091\le k\le 10^9
  • 1liri1091\le l_i\le r_i\le 10^9
  • 1pik1\le p_i\le k