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