Pagini recente » Cod sursa (job #237536) | Cod sursa (job #1812436) | Cod sursa (job #520814) | Cod sursa (job #1034338) | Cod sursa (job #1783558)
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAXN 100000
#define BUF_SIZE 131072
using namespace std;
struct trupa
{
int st,dr;
}v[MAXN];
int d[MAXN],pos=BUF_SIZE,n,poz[MAXN];
inline int lung(int i)
{
return v[poz[i]].dr-v[poz[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;
}
bool cond(int a,int b)
{
return v[a].dr<v[b].dr || (v[a].dr==v[b].dr && v[a].st<v[b].st);
}
inline int cbin(int x)
{
int i,j,mij;
i=0;j=n-1;
while(i<=j)
{
mij=(i+j)/2;
if(v[poz[mij]].dr==x)
{
while(v[poz[mij]].dr==x)
mij++;
return mij-1;
}
if(v[poz[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();
poz[i]=i;
}
sort(poz,poz+n,cond);
d[0]=lung(0);
for(i=1;i<n;i++)
d[i]=max(d[i-1],d[cbin(v[poz[i]].st)]+lung(i));
fprintf(fout,"%d",d[n-1]);
fclose(fin);
fclose(fout);
return 0;
}