传说中用线段树刷。。
查看原帖
传说中用线段树刷。。
184
shutdown楼主2013/7/3 16:31

奇葩的第五点运行时错误。。怎么回事orz。。

#include <iostream>
#include <stdio.h>
using namespace std;
struct node{int aa,bb,cov;};
node tree[20000001];
int a[5001],b[5001];
int i,j,k,l,m,n,p,q,x,y,z,tmp1,tmp2,maxx,minn;
void buildtree(int l,int r,int x)
{
     int mid;
     tree[x].aa=l;
     tree[x].bb=r;
     mid=(l+r)/2;
     //cout<<l<<' '<<r<<endl; system("pause");
     if (r-l>1)
     {
               buildtree(l,mid,x*2);
               buildtree(mid,r,x*2+1);
     }
}
void cover(int l,int r,int x)
{
     int i,j,mid;
     mid=(tree[x].aa+tree[x].bb)/2;
     if ((l==tree[x].aa)&&(r==tree[x].bb)){tree[x].cov=1; return;} else
     if (r<=mid){cover(l,r,x*2);} else
     if (l>=mid){cover(l,r,x*2+1);} else
     {
                                    cover(l,mid,x*2);
                                    cover(mid,r,x*2+1);
     }
}
void countt(int x)
{
     int i,j;
     if (tree[x].cov==1){tmp1=tmp1+tree[x].bb-tree[x].aa; if (tmp2>minn) minn=tmp2; tmp2=0; return;};
     //if (tree[x].aa>=300){cout<<tree[x].aa<<' '<<tree[x].bb<<' '<<tmp1<<' '<<tmp2<<' '<<maxx<<' '<<minn<<endl; system("pause");};
     if ((tree[x].cov==0)&&(tree[x].bb-tree[x].aa==1)&&(tree[x].aa>=q)&&(tree[x].bb<=p)){ if (tmp1>maxx){maxx=tmp1;}; tmp1=0; tmp2++;};
     if (tree[x].bb-tree[x].aa>1)
     {
                                 i=tmp1; j=tmp2;
                                 countt(x*2);
                                 countt(x*2+1);
     }
}
int main()
{
    scanf("%d",&n);
    buildtree(1,1000000,1);
    p=0; q=2000000000;
    for (i=1; i<=n; i++)
    {
        scanf("%d%d",&x,&y);
        cover(x,y,1);
        if (y>p) p=y;
        if (x<q) q=x;
    }
    maxx=0; minn=0;
    tmp1=0; tmp2=0;
    countt(1);
    if (tmp1>maxx) maxx=tmp1;
    if (tmp2>minn) minn=tmp2;
    printf("%d %d",maxx,minn);
    system("pause");
    return 0;
}

2013/7/3 16:31
加载中...