Pagini recente » Cod sursa (job #867402) | Cod sursa (job #2899459) | Cod sursa (job #1633186) | Cod sursa (job #1788) | Cod sursa (job #1780075)
#include <stdio.h>
#include <ctype.h>
#define max(a,b) a>b? a:b
#define MAXN 100000
#define BUF_SIZE 131072
struct trupa
{
int st,dr;
}v[MAXN];
int d[MAXN],pos=BUF_SIZE,n;
inline int lung(int i)
{
return v[i].dr-v[i].st;
}
FILE *fin,*fout;
char buf[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,p;
i=start;j=stop;p=v[(i+j)/2].dr;
while(i<=j)
{
while(v[i].dr<p)
i++;
while(v[j].dr>p)
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);
}
inline int cbin(int x)
{
int i,j,mij;
i=0;j=n-1;
while(i<=j)
{
mij=(i+j)/2;
if(v[mij].dr==x)
{
while(v[mij].dr==x)
mij++;
return mij-1;
}
if(v[mij].dr<x)
i=mij+1;
else
j=mij-1;
}
return j;
}
int main()
{
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
int i;
n=read();
for(i=0;i<n;i++)
{
v[i].st=read();
v[i].dr=read();
}
myqsort(0,n-1);
d[0]=lung(0);
for(i=1;i<n;i++)
d[i]=max(d[i-1],d[cbin(v[i].st)]+lung(i));
fprintf(fout,"%d",d[n-1]);
fclose(fin);
fclose(fout);
return 0;
}