Pagini recente » Cod sursa (job #511243) | Cod sursa (job #2639745) | Cod sursa (job #2363090) | Cod sursa (job #1862279) | Cod sursa (job #256843)
Cod sursa(job #256843)
#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;
}