Cod sursa(job #256843)

Utilizator SheepBOYFelix Liviu SheepBOY Data 12 februarie 2009 12:11:09
Problema Stergeri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include<stdio.h>  
#include<stdlib.h>
struct TETRA{  
    int u,l,b;  
};  
TETRA table[100000];  
int compar(const void *a,const void *b)
{
	TETRA x=*(TETRA*)a,y=*(TETRA*)b;
	if(x.l>y.l)
		return 1;
	if(x.l==y.l)
		return 0;
	if(x.l<y.l)
		return -1;
}
int nt;  
inline int esti_al_meu(int a,TETRA intr)  
{  
    if(a>=intr.l&&a<=intr.u)  
        return 1;  
    if(a>intr.u)  
        return 0;  
    if(a<intr.l)  
        return -1;  
}  
inline int intersect(int l,int u,TETRA &intrv)  
{  
    int aux;
	if(u>=intrv.l&&l<=intrv.l)	
    {  
        aux=(u+1)-l+intrv.b;  
        intrv.l=l;  
        intrv.u=(u>intrv.u)?u:intrv.u;  
        intrv.b=aux;  
    }  
    if(l>=intrv.l&&l<=intrv.u&&u>=intrv.u)  
    {  
		if(l>intrv.l)
		{
		table[nt].u=u;
		table[nt].l=l;
		table[nt].b=intrv.b+u+1-l;
		++nt;
        intrv.u=l-1;  
		}	
		else
		{
			table[nt].u=u;
			table[nt].l=l;
			table[nt].b=intrv.b+u+1-l;
			++nt;
			intrv.u=u;
			intrv.b+=u+1-l;
		}
    }  
    if((u+u+1-l)>=intrv.l&&l<=intrv.l)  
    {  
        aux=u-1;  
        while((aux+u+1-l)>=intrv.l&&aux>=l)  
            --aux;  
        ++aux;  
        table[nt].l=aux;  
        table[nt].u=u;  
        table[nt++].b=u+1-l+intrv.b;  
        if(aux>l)  
        {  
        table[nt].l=l;  
        table[nt].u=aux-1;  
        table[nt++].b=u+1-l;  
        }  
    } 
return 0;	
}  
int main()  
{  
    int entr,aux,ax,i,u,l,n,m,k;  
    freopen("stergeri.in","r",stdin);  
    freopen("stergeri.out","w",stdout);  
    scanf("%d%d%d",&n,&m,&k);  
    while(m)  
    {  
        scanf("%d%d",&l,&u);  
            entr=0;
			
        for(i=0;i<nt;++i)
		{			
            ax=intersect(l,u,table[i]);
			if(!ax)		
            {  
                entr=1;  
                break;  
            }  
			else
			{
				entr=1;
			}
		}
        if(!entr)  
        {  
            table[nt].l=l;  
            table[nt].u=u;  
            table[nt++].b=u+1-l;  
        }  
            --m;  
    }  
    int last=-1; 
	//qsort(table,nt,sizeof(table[0]),compar);	
    entr=0;  
    for(i=0;i<nt;++i)  
    {  
        aux=esti_al_meu(k,table[i]);  
        if(!aux)  
        last=i;  
        if(aux>0)  
            {printf("%d",k+table[i].b);entr=1;break;}  
        if(aux<0)  
            break;  
    } 
if(!entr)
{	
    if(!entr&&last>-1)  
    printf("%d",k+table[last].b);  
    else  
        printf("%d",k);  
}  
	return 0;  
}