Pagini recente » Cod sursa (job #1716308) | Cod sursa (job #2114092) | Cod sursa (job #2828370) | Cod sursa (job #3269159) | Cod sursa (job #2513828)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int N;
struct concert{
int A,B,val;
}v[100005];
int q[200005], d[100005], Tmax,Q,poz,rez;
map <int, int> M;
inline bool cmp(concert A, concert B){
if(A.B==B.B)return A.A>B.A;
else return A.B<B.B;
}
void CautBin(int st, int dr)
{int mid=(st+dr)/2;
if(st==dr) poz=mid;
else {
if(v[mid].B>=Q)CautBin(st,mid);
else CautBin(mid+1,dr);
}
}
int main()
{fin>>N;
for(int i=1;i<=N;i++){
fin>>v[i].A>>v[i].B;
q[i*2-1]=v[i].A;
q[i*2]=v[i].B;
v[i].val=v[i].B-v[i].A;
}
sort(q+1,q+2*N+1);
for(int i=1;i<=2*N;i++){
if(q[i]>q[i-1])M[q[i]]=M[q[i-1]]+1;
else M[q[i]]=M[q[i-1]];
Tmax=max(Tmax,M[q[i]]);
}
for(int i=1;i<=N;i++){
v[i].A=M[v[i].A];
v[i].B=M[v[i].B];
}
sort(v+1,v+N+1,cmp);
for(int i=1;i<=Tmax;i++){
d[i]=d[i-1];
Q=i;
CautBin(1,N);
//cout<<poz<<"\n";
for(int j=poz;v[j].B==i;j++){
d[i]=max(d[i],d[v[j].A]+(v[j].val));
//cout<<"AHH\n";
}
rez=max(rez,d[i]);
}
fout<<rez;
}