9
27
2015
0

4143: [AMPPZ2014]The Lawyer

4143: [AMPPZ2014]The Lawyer

Time Limit: 10 Sec  Memory Limit: 256 MBSec  Special Judge
Submit: 345  Solved: 189
[Submit][Status][Discuss]

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

 

Source

    我会告诉你我想刷AMPPZ是因为看到了这道水题吗。。。。

    记录一下每天最早结束和最迟开始的会议就可以了。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25;
int n,m,a,b,d,Max[N],Min[N],MaxI[N],MinI[N];
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9'){if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
int main(){
	n = read();m = read();
	for (int i=1;i<=m;i++) Min[i] = 1e9;
	for (int i=1;i<=n;i++){
		a = read();b = read();d = read();
		if (Min[d]>b) {Min[d] = b;MinI[d] = i;}
		if (Max[d]<a) {Max[d] = a;MaxI[d] = i;}
	}
	for (int i=1;i<=m;i++)
		if (Min[i]<Max[i]) printf("TAK %d %d\n",MinI[i],MaxI[i]);
		else printf("NIE\n");
}
Category: BZOJ题解 | Tags: | Read Count: 345

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com