ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1019. Перекрашивание прямой

I have checked all the tests on the board, but I still got WA on test#3..Help me!!
Послано akademi 21 апр 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;
}