Pagini recente » Cod sursa (job #1380837) | Cod sursa (job #1186934) | Cod sursa (job #1140804) | Cod sursa (job #2699504) | Cod sursa (job #854264)
Cod sursa(job #854264)
#include<fstream>
#include<cassert>
#include<algorithm>
#define NMAX 100004
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int N ;
struct interval{ int st, dr;};
interval v[NMAX];
long long d[NMAX];
struct cmp {
bool operator ()(const interval &a, const interval &b) const{
return a.dr < b.dr;
}
};
void Read() {
fin >>N;
for(int i = 1; i <= N; i++)
fin >>v[i].st >> v[i].dr;
}
int binary_search(int k,int p){
int step = 1, pos = 0;
for(step ; step <= p; (step <<= 1));
for(pos = 0; step ; (step >>= 1))
if(pos + step <= p && v[pos + step].dr <= k)
pos += step;
return pos;
}
void Solve() {
sort (v + 1, v + 1 + N, cmp());
d[1] = v[1].dr - v[1].st;
for(int i = 2; i <= N; i++)
d[i] = max (d[i - 1], d[binary_search(v[i].st,i)] + v[i].dr - v[i].st);
}
void Print() {
fout << d[N];
}
int main(){
Read ();
Solve ();
Print ();
return 0;
}