Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom11月前

12/6
21:07
暴力

[bzoj 4143] [AMPPZ2014]The Lawyer

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

Byteasar要制订m天的会议计划,一共有n场会议,第i场会议开始于第d[i]天的第a[i]秒,结束于第d[i]天的第b[i]秒。
对于每一天,请找出这一天的两场会议i,j,使得它们不冲突,即不存在一个数k同时满足a[i]<=k<=b[i]以及a[j]<=k<=b[j]。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行包含两个正整数n,m(2<=n<=500000,1<=m<=20),表示会议的场数和天数。
接下来n行,每行包含三个正整数a[i],b[i],d[i](1<=a[i]<b[i]<=80000000,1<=d[i]<=m),描述一场会议。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出m行。第i行输出第i天的答案,如果无解,输出NIE,否则输出TAK,然后输出这一天参加的两场会议的编号,
如有多组解,输出任意一组。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

6 3
3 5 1
2 4 2
1 8 1
6 7 3
3 5 2
7 12 1

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

TAK 1 6
NIE
NIE

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

考虑每天最早结束的一场的结束时间以及最晚开始的一场的开始时间,如果结束时间早于开始时间就是满足条件的

 

[bzoj 4143] [AMPPZ2014]The Lawyer