Pagini recente » Cod sursa (job #2321164) | Cod sursa (job #1120545) | Cod sursa (job #1249853) | Cod sursa (job #1900272) | Cod sursa (job #1227744)
#include<stdio.h>
#include<algorithm>
#define N 100000
struct elem{int start;int end;} v[N];
bool cmp(elem a, elem b){
if(a.start<b.start)
return true;
if(a.start>b.start)
return false;
if(a.end<a.end)
return true;
else return false;
}
int best[N];
inline int bsearch(int dr){
int st=0,mij=(st+dr)/2,max=0,poz=dr+1;
while(st<=dr){
if(v[poz].start<v[mij].end)
dr=mij-1;
else{
if(v[mij].end<=v[poz].start)
max=mij;
st=mij+1;
}
mij=(st+dr)/2;
}
return best[max];
}
inline int maxof2(int a,int b){
if(a<b)
return b;
return a;
}
int main(){
FILE *fin,*fout;
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
int n;
fscanf(fin,"%d",&n);
int i;
for(i=0;i<n;i++){
fscanf(fin,"%d%d",&v[i].start,&v[i].end);
v[i].start--,v[i].end--;
}
std::sort(v,v+n,cmp);
best[0]=v[0].end-v[0].start;
for(i=1;i<n;i++){
int poz=bsearch(i-1);
best[i]=maxof2(best[i-1],v[i].end-v[i].start+poz);
}
fprintf(fout,"%d",best[n-1]);
return 0;
}