I have checked all the tests on the board, but I still got WA on test#3..Help me!!
Posted by
akademi 21 Apr 2005 09:29
/* ural1019 */
#include<cstdio>
#include<string>
const long maxn=5010;
typedef struct ele
{
long data;
char ch;
}ele;
long sz[maxn*2],a[maxn*2],b[maxn*2];
long p;
ele line[2*maxn];
char c[maxn*2];
void sort(long l,long t)
{
long i,j,tmp;
i=l;j=t;tmp=sz[i];
while(i<j)
{
while(i<j && sz[j]>tmp) j--;
if(i<j)
{
sz[i]=sz[j];
i++;
}
while(i<j && sz[i]<tmp) i++;
if(i<j)
{
sz[j]=sz[i];
j--;
}
}
sz[i]=tmp;
if(l<i-1) sort(l,i-1);
if(i+1<t) sort(i+1,t);
}
long find(long x)
{
long low,hig,mid;
low=1;hig=p-1;mid=(low+hig)/2;
while(low<=hig)
{
mid=(low+hig)/2;
if(line[mid].data==x) return mid;
if(line[mid].data>x) hig=mid-1;
else low=mid+1;
}
return mid;
}
void init()
{
long i,j,n,p1,p2;
memset(sz,0,sizeof(sz));
memset(line,0,sizeof(line));
scanf("%ld",&n);
for(i=1;i<=n;i++)
{
scanf("%ld%ld%c%c",&a[i],&b[i],&c[i],&c[i]);
sz[2*i]=a[i];sz[2*i+1]=b[i];
}
sz[1]=0;sz[2*n+2]=1000000000;
sort(1, 2*n+2);
p=1;
for(i=1;i<=2*n+2;i++)
if(sz[i]!=line[p-1].data) line[p++].data=sz[i];
for(i=1;i<p-1;i++) line[i].ch='w';
line[p-1].ch='b';
for(i=1;i<=n;i++)
{
p1=find(a[i]);
p2=find(b[i]);
for(j=p1;j<p2;j++) line[j].ch=c[i];
}
}
void work()
{
long ansl,ansr,tl,tmax,best,i;
tl=0;
ansl=ansr=-1;
tmax=best=-1;
for(i=1;i<p;i++)
if(line[i].ch=='w')
{
if(tmax==0) tl=i;
tmax=line[i+1].data-line[tl].data;
if(tmax>best)
{
best=tmax;
ansl=tl;
ansr=i;
}
}else tmax=0;
printf("%ld %ld\n",line[ansl].data,line[ansr+1].data);
}
int main()
{
init();
work();
return 0;
}