1436.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"memory.h"
#include"algorithm"
using namespace std;

int y1[8000],y2[8000],x[8000],index[8000];
int l[16000],n;
int *edge[8000];

int cmp(int a,int b)
{return x[a]<x[b];}

void init()
{int i;

cin>>n;

//memset(edge,0,n*sizeof(int *));

for(i=0;i<n;i++)
{cin>>y1[i]>>y2[i]>>x[i];
y1[i]*=2;y2[i]*=2;
index[i]=i;}

sort(&index[0],&index[n],cmp);

}

void built()
{char sign[8000];int i,j,num;

memset(l,-1,16000*sizeof(int));
for(i=0;i<n;i++)
{	memset(sign,0,8000*sizeof(char));

	for(j=y1[index[i]];j<=y2[index[i]];j++)
	{if(l[j]>=0)sign[l[j]]=1;
	l[j]=i;
	}

	for(num=0,j=0;j<n;j++)
	if(sign[j])num++;

	edge[i]=new int[num+1];

	for(num=0,j=0;j<n;j++)
	if(sign[j])edge[i][num++]=j;

	edge[i][num]=-1;

}
}

long answer;

/*
void find()
{long sign[8000],i,sb=1;
int queue[8100],head,tail,now;
answer=0;
memset(sign,0,8000*sizeof(long));

while(1)
{for(i=n-1;i>=0;i--)if(!sign[i])break;
 if(i<0)break;
 
 sign[i]=sb;head=0,tail=0;
 queue[tail++]=i;
while (head!=tail)
{now=queue[head++];
 for(i=0;edge[now][i]!=-1;i++)
 {if(sign[edge[now][i]]==sign[now])answer++;
 else if(sign[edge[now][i]]<sign[now])
		{sign[edge[now][i]]=sign[now]+1;queue[tail++]=edge[now][i];}
 }
}
sb++;
}
return ;
}*/

void find()
{int i,j,k;
char sign[8000];
answer=0;
for(i=n-1;i>=0;i--)
{memset(sign,0,n*sizeof(char));
for(j=0;edge[i][j]!=-1;j++)sign[edge[i][j]]=1;

for(j=0;edge[i][j]!=-1;j++)
for(k=0;edge[edge[i][j]][k]!=-1;k++)
{if(sign[edge[edge[i][j]][k]])answer++;
}

}

}




int main()
{int t;
cin>>t;
while(t--)
{init();
 built();
 find();
 cout<<answer<<endl;
}
return 0;
}