Pagini recente » Cod sursa (job #366303) | Cod sursa (job #2182963) | Cod sursa (job #2983719) | Cod sursa (job #1416652) | Cod sursa (job #1779955)
#include <stdio.h>
#include <ctype.h>
#define max(a,b) a>b? a:b
#define BUF_SIZE 131072
struct trupa
{
int st,dr;
}v[100000];
inline int lung(int i)
{
return v[i].dr-v[i].st;
}
FILE *fin,*fout;
char buf[BUF_SIZE];
int pos=BUF_SIZE;
inline char getch()
{
if(pos==BUF_SIZE)
fread(buf,BUF_SIZE,1,fin),pos=0;
return buf[pos++];
}
inline int read()
{
int x=0;
char ch=getch();
while(!isdigit(ch))
ch=getch();
do
{
x=x*10+ch-'0';
ch=getch();
} while(isdigit(ch));
return x;
}
inline void interschimb(int *a,int *b)
{
int aux=*a;
*a=*b;*b=aux;
}
void myqsort(int start,int stop)
{
int i,j,p1,p2;
i=start;j=stop;p1=v[(i+j)/2].st;p2=v[(i+j)/2].dr;
while(i<=j)
{
while(v[i].st<p1)
i++;
if(v[i].st==p1)
while(v[i].dr<p2)
i++;
while(v[j].st>p1)
j--;
if(v[j].st==p1)
while(v[j].dr>p2)
j--;
if(i<=j)
{
interschimb(&v[i].st,&v[j].st);
interschimb(&v[i].dr,&v[j].dr);
i++;j--;
}
}
if(j>start)
myqsort(start,j);
if(i<stop)
myqsort(i,stop);
}
int main()
{
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
int n,i,d1,d2;
n=read();
for(i=0;i<n;i++)
{
v[i].st=read();
v[i].dr=read();
}
myqsort(0,n-1);
d1=lung(0);
for(i=1;i<n;i++)
{
if(v[i].st<v[i-1].dr)
d2=max(d1,d1+lung(i)-lung(i-1));
else
d2=d1+lung(i);
d1=d2;
}
fprintf(fout,"%d",d2);
fclose(fin);
fclose(fout);
return 0;
}