| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:线段树太烦琐。。直接用链表模拟一张一张贴。。不过速度慢了点。。750ms...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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator