Pagini recente » Cod sursa (job #291507) | Cod sursa (job #185955) | Cod sursa (job #3170864) | Cod sursa (job #1045920) | Cod sursa (job #730853)
Cod sursa(job #730853)
#include <fstream>
#include <algorithm>
#define LE 100005
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct interval {int x,y;}v[LE],a[LE];
int i,n,pozitie,timp,k,MAX ;
int comp(interval e ,interval c){
if (e.y==c.y) return e.x>c.x;
return e.y<c.y;
}
int caut(int val){
int step,poz;
for(step=1;step<=k;step*=2);
for(poz=0;step;step/=2)
if (poz+step<=k&&a[poz+step].y<=val)
poz+=step;
return poz;
}
int main(){
f>>n;
for(i=1;i<=n;++i) f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,comp);
for(i=1;i<=n;++i){
pozitie=caut(v[i].x);
timp=a[pozitie].x+v[i].y-v[i].x;
if (a[k].x<timp&&a[k].y==v[i].y) a[k].x=timp;
if (a[k].x!=v[i].y&&a[k].x<timp)
{a[++k].x=timp;a[k].y=v[i].y;}
}
for(i=1;i<=k;++i)
if (a[i].x>MAX) MAX=a[i].x;
g<<MAX<<'\n';
f.close();g.close();
return 0;
}