Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:线段树太烦琐。。直接用链表模拟一张一张贴。。不过速度慢了点。。750ms...

Posted by pengshihui at 2010-09-01 21:44:52 on Problem 2528
In Reply To:Re:线段树太烦琐。。直接用链表模拟一张一张贴。。不过速度慢了点。。750ms... Posted by:blue_fog at 2010-09-01 20:14:06
#include "stdio.h"
#include "memory.h"
#include "malloc.h"
struct node1
{
	int l,r;
	node1 * next;
};
struct node
{
	node * next;
	node1 * next1;
};
node temp[10000];
node1 te[300000];
int index,ind;
node * list,* p,*q;
node1 * p1,*q1,*r1,*m;
int count;

void insert(node * r)
{
	q=list;
	p=list->next;
	r1=r->next1;
	while(p)
	{
		p1=q1=p->next1;
		while(p1)
		{
			if(r1->l<=p1->l&&r1->r>=p1->r)
			{
				if(p1==p->next1)
				{
					p->next1=p1->next;
					q1=p1=p->next1;
				}
				else
				{
					q1->next=p1->next;
					p1=q1->next;
				}
			}
			else if(r1->l>=p1->r||r1->r<=p1->l){q1=p1;p1=p1->next; continue;}
			else if(r1->l>p1->l&&r1->r<p1->r)
			{
				m=te+ind++;
				m->l=r1->r;
				m->r=p1->r;
				m->next=p1->next;
				p1->next=m;
				p1->r=r1->l;
				q1=m;
				p1=m->next;
			}
			else if(r1->r<p1->r)
			{
				p1->l=r1->r;
				q1=p1;
				p1=p1->next;
			}
			else
			{
				p1->r=r1->l;
				q1=p1;
				p1=p1->next;
			}
		}
		if(p->next1==NULL)
		{
			count--;
			q->next=p=p->next;
		}
		else
		{
			q=p;
			p=p->next;
		}
	}
	r->next=list->next;
	list->next=r;
}
void initialize()
{
	ind=index=0;
	memset(temp,0,sizeof(temp));
	list->next=NULL;
}
int main(void)
{
	int i,j,t,n,a,b;
	list=(node *)malloc(sizeof(node));
	memset(list,0,sizeof(node));
	node * p;
	node1 * q;
	scanf("%d",&t);
	for(i=0;i<t;++i)
	{
		initialize();
		scanf("%d",&n);
		count=n;
		for(j=0;j<n;++j)
		{
			scanf("%d%d",&a,&b);
			p=temp+index++;
			p->next1=q=te+ind++;
			q->l=a;q->r=b+1;q->next=NULL;
			insert(p);
		}
		printf("%d\n",count);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator