Pagini recente » Cod sursa (job #2167068) | Cod sursa (job #1739942) | Cod sursa (job #1246705) | Cod sursa (job #2123147) | Cod sursa (job #1781719)
#include <stdio.h>
#include <algorithm>
#define MAXN 100000
struct concert{
int b, e;
} v[MAXN+1];
int pa[MAXN+1], d[MAXN+1], PUTERE=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=PUTERE, rez=0;
for(pas/=2;pas>0;pas/=2)
if(v[pa[rez+pas]].e<=v[pa[x]].b)
rez+=pas;
return rez;
}
inline int maxim(int a, int b){
return a<b ? b:a;
}
int main()
{
int n, i;
FILE *fi=fopen("heavymetal.in", "r"), *fo=fopen("heavymetal.out", "w");
fscanf(fi, "%d", &n);
while(PUTERE<n)
PUTERE*=2;
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);
for(i=1;i<=n;i++)
d[pa[i]]=maxim(d[pa[CB(i)]]+v[pa[i]].e-v[pa[i]].b,d[pa[i-1]]);
fprintf(fo, "%d", d[n]);
fclose(fi);
fclose(fo);
return 0;
}