Cod sursa(job #126847)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 22 ianuarie 2008 21:40:17
Problema Stergeri Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<stdio.h>
long n,a[100001],b[100001];

int partitionare(int st, int dr)
{
int i,j,m,pivot,aux;
m=(st+dr)>>1;
pivot=a[m];
i=st-1;
j=dr+1;
while(1)
  {
  do{++i;}while(a[i]<pivot);
  do{--j;}while(a[j]>pivot);
  if(i<j)
    {
    aux=a[i];
    a[i]=a[j];
    a[j]=aux;
    aux=b[i];
    b[i]=b[j];
    b[j]=aux;
    }
  else
    return j;
  }
}


void quicks(int st,int dr)
{
int p;
if(st<dr)
  {
  p=partitionare(st,dr);
  quicks(st,p);
  quicks(p+1,dr);
  }
}


int main()
{
long m,k,i;
freopen("stergeri.in","r",stdin);
freopen("stergeri.out","w",stdout);
scanf("%ld%ld%ld",&n,&m,&k);
for(i=1;i<=m;i++)
  scanf("%ld%ld",&a[i],&b[i]);
quicks(1,m);
if(a[1]>k)
  {
  printf("%ld",k);
  return 0;
  }
i=1;
while(a[i]<=k && i<=m)
  {
  k=k+b[i]-a[i]+1;
  i++;
  }
printf("%ld",k);
return 0;
}