 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| 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 | |||||||||
附wa代码。。。In Reply To:做了一个星期了,修改了很多个版本,从re->tle->wa,自己设计的数据都没问题,已经不知道哪里出错了..希望路过的好心人帮忙吧~ Posted by:shiroi at 2007-05-18 00:51:13 #include<stdio.h>
#define maxn 65600
struct seg{
int ll,rr,cov; bool inv;
seg(int l=0,int r=0,int ccov=-1,bool iinv=0) { ll=l,rr=r,cov=ccov,inv=iinv;}
}segt[8*maxn];
seg ans[maxn*2];
int size=0;
void build(int l,int r,int ind)
{
segt[ind].ll=l; segt[ind].rr=r; segt[ind].cov=-1; segt[ind].inv=0;
if(r-l>1) {
int mid=(l+r)/2;
build(l,mid,ind+ind);
build(mid,r,ind+ind+1);
}
}
void segunion(int l,int r,int ind)
{
if(l<=segt[ind].ll&&r>=segt[ind].rr) {
segt[ind].cov=1; segt[ind].inv=0; return ;
}
if(segt[ind].inv==0) {
if(segt[ind].cov==1) return;
if(segt[ind].cov==-1) {
segt[ind+ind].cov=segt[ind+ind+1].cov=-1; segt[ind+ind].inv=segt[ind+ind+1].inv=0;
}
}
else {
if(segt[ind].cov==-1) {
segt[ind].cov=1; segt[ind].inv=0; return;
}
segt[ind].inv=0;
if(segt[ind].cov==1) {
segt[ind+ind].cov=segt[ind+ind+1].cov=-1; segt[ind+ind].inv=segt[ind+ind+1].inv=0;
}
if(segt[ind].cov==0) {
segt[ind+ind].inv=(segt[ind+ind].inv+1)&1; segt[ind+ind+1].inv=(segt[ind+ind+1].inv+1)&1;
}
}
if(l<(segt[ind].ll+segt[ind].rr )/2) segunion(l,r,ind+ind);
if(r>(segt[ind].ll+segt[ind].rr )/2) segunion(l,r,ind+ind+1);
if(segt[ind+ind].cov*segt[ind+ind+1].cov==1)
segt[ind].cov=segt[ind+ind].cov;
else segt[ind].cov=0;
}
void segsub(int l,int r,int ind)
{
if(l<=segt[ind].ll&&r>=segt[ind].rr) {
segt[ind].cov=-1; segt[ind].inv=0; return ;
}
if(segt[ind].inv==0) {
if(segt[ind].cov==-1) return ;
if(segt[ind].cov==1) {
segt[ind+ind].cov=segt[ind+ind+1].cov=1; segt[ind+ind].inv=segt[ind+ind+1].inv=0;
}
}
else {
if(segt[ind].cov==1) {
segt[ind].cov=-1; segt[ind].inv=0; return ;
}
segt[ind].inv=0;
if(segt[ind].cov==-1) {
segt[ind+ind].cov=segt[ind+ind+1].cov=1; segt[ind+ind].inv=segt[ind+ind+1].inv=0;
}
if(segt[ind].cov==0) {
segt[ind+ind].inv=(segt[ind+ind].inv+1)&1; segt[ind+ind+1].inv=(segt[ind+ind+1].inv+1)&1;
}
}
if(l<(segt[ind].ll+segt[ind].rr)/2) segsub(l,r,ind+ind);
if(r>(segt[ind].ll+segt[ind].rr)/2) segsub(l,r,ind+ind+1);
if(segt[ind+ind].cov*segt[ind+ind+1].cov==1)
segt[ind].cov=segt[ind+ind].cov;
else segt[ind].cov=0;
}
void segxor(int l,int r,int ind)
{
if(l<=segt[ind].ll&&r>=segt[ind].rr) {
if(segt[ind].cov==0) {
segt[ind].inv=(segt[ind].inv+1)&1; return ;
}
if(segt[ind].inv==0)
segt[ind].cov=-segt[ind].cov;
segt[ind].inv=0;
return ;
}
if(segt[ind].inv==0) {
if(segt[ind].cov!=0) {
segt[ind+ind].cov=segt[ind+ind+1].cov=segt[ind].cov;
segt[ind+ind].inv=segt[ind+ind+1].inv=0;
}
}
else {
if(segt[ind].cov!=0) {
segt[ind+ind].cov=segt[ind+ind+1].cov=-segt[ind].cov;
segt[ind+ind].inv=segt[ind+ind+1].inv=0;
}
else {
segt[ind+ind].inv=(segt[ind+ind].inv+1)&1; segt[ind+ind+1].inv=(segt[ind+ind+1].inv+1)&1;
}
segt[ind].inv=0;
}
if(l<(segt[ind].ll+segt[ind].rr)/2) segxor(l,r,ind+ind);
if(r>(segt[ind].ll+segt[ind].rr)/2) segxor(l,r,ind+ind+1);
if(segt[ind+ind].cov*segt[ind+ind+1].cov==1)
segt[ind].cov=segt[ind+ind].cov;
else segt[ind].cov=0;
}
void stat(int ind)
{
if(segt[ind].cov==1&&segt[ind].inv==0||segt[ind].cov==-1&&segt[ind].inv==1) {
if(size==0) ans[size++]=seg(segt[ind].ll,segt[ind].rr);
else {
if(segt[ind].ll<=ans[size-1].rr)
ans[size-1].rr=segt[ind].rr;
else ans[size++]=seg(segt[ind].ll,segt[ind].rr);
}
return ;
}
else if(segt[ind].cov==-1&&segt[ind].inv==0||segt[ind].cov==1&&segt[ind].inv==1) return ;
if(segt[ind].rr-segt[ind].ll>1) {
if(segt[ind].inv==1) {
segt[ind+ind].inv=(segt[ind+ind].inv+1)&1; segt[ind+ind+1].inv=(segt[ind+ind+1].inv+1)&1;
segt[ind].inv=0;
}
stat(ind+ind); stat(ind+ind+1);
}
}
int main()
{
char cmd,bra1,bra2,dot;
int a,b;
build(0,2*65535+1,1);
while(scanf("%c %c%d,%d%c\n",&cmd,&bra1,&a,&b,&bra2)==5) {
if(bra1=='[') a=a+a; else a=a+a+1;
if(bra2==']') b=b+b+1; else b=b+b;
if(cmd=='U'&&b>a)
segunion(a,b,1);
else if(cmd=='I') {
if(a>0)
segsub(0,a,1);
if(b<2*65535+1)
segsub(b,2*65535+1,1);
}
else if(cmd=='D'&&b>a)
segsub(a,b,1);
else if(cmd=='C') {
if(a>0)
segsub(0,a,1);
if(b<2*65535+1)
segsub(b,2*65535+1,1);
if(b>a)
segxor(a,b,1);
}
else if(cmd=='S'&&b>a)
segxor(a,b,1);
}
stat(1);
if(size==0) {
printf("empty set\n"); return 0;
}
for(a=0;a<size-1;a++) {
if(ans[a].ll%2==0) printf("[%d,",ans[a].ll/2);
else printf("(%d,",ans[a].ll/2);
if(ans[a].rr%2==0) printf("%d) ",ans[a].rr/2);
else printf("%d] ",ans[a].rr/2);
}
if(ans[a].ll%2==0) printf("[%d,",ans[a].ll/2);
else printf("(%d,",ans[a].ll/2);
if(ans[a].rr%2==0) printf("%d)\n",ans[a].rr/2);
else printf("%d]\n",ans[a].rr/2);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
