Pagini recente » Cod sursa (job #2800184) | Cod sursa (job #1363797) | Cod sursa (job #2704982) | Cod sursa (job #1148025) | Cod sursa (job #1699453)
#include <algorithm>
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct qq {
long long st , en;
} v[NMAX];
long long dp[NMAX];
long long n;
bool comp(qq a , qq b) {
return a.en < b.en || (a.en = b.en && a.st < b.st);
}
long long caut_bin(long long val);
int main() {
f >> n;
for(int i = 1 ; i <= n ; ++i) {
f >> v[i].st >> v[i].en;
}
sort(v + 1 , v + n + 1 , comp);
for(int i = 1 ; i <= n ; ++i) {
long long p = caut_bin(v[i].st);
dp[v[i].en] = dp[v[p].en] + v[i].en - v[i].st;
}
g << dp[v[n].en];
return 0;
}
long long caut_bin(long long val) {
long long i , p = 0;
for(i = 1 ; i <= n ; i <<= 1);
while(i) {
if(i + p <= n && v[i + p].en <= val) {
p += i;
}
i >>= 1;
}
return p;
}