Pagini recente » Cod sursa (job #1440803) | Cod sursa (job #445259) | Cod sursa (job #1634980) | Cod sursa (job #1095129) | Cod sursa (job #1780395)
#include <stdio.h>
#include <algorithm>
#define MAXN 100000
struct concert{
int b, e;
} v[MAXN+1];
int pa[MAXN+1], d[MAXN+1];
bool comp(int x, int y){
if(v[x].e<v[y].e)
return true;
else if(v[x].e==v[y].e && v[x].b<v[y].b)
return true;
return false;
}
int CB(int x){
int pas=1, rez=0;
while(pas<x)
pas*=2;
for(pas/=2;pas>0;pas/=2)
if(v[pa[rez+pas]].e<=v[pa[x]].b)
rez+=pas;
return rez;
}
int main()
{
int n, i, max;
FILE *fi=fopen("heavymetal.in", "r"), *fo=fopen("heavymetal.out", "w");
fscanf(fi, "%d", &n);
for(i=1;i<=n;i++){
fscanf(fi, "%d%d", &v[i].b, &v[i].e);
pa[i]=i;
}
std::sort(pa+1,pa+n+1,comp);
max=0;
for(i=1;i<=n;i++){
d[pa[i]]=d[pa[CB(i)]]+v[pa[i]].e-v[pa[i]].b;
if(d[pa[i]]>max)
max=d[pa[i]];
}
fprintf(fo, "%d", max);
fclose(fi);
fclose(fo);
return 0;
}