Pagini recente » Cod sursa (job #221037) | Cod sursa (job #1070265) | Cod sursa (job #1175275) | Cod sursa (job #1604732) | Cod sursa (job #2112138)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("heavymetal.in");
ofstream fo("heavymetal.out");
const int lim = 1e5;
struct interval{
int st, dr;
} v[lim + 1];
int pa[lim + 1], d[lim + 1];
bool cmp(interval a, interval b){
return a.dr < b.dr;
}
inline int CB(int x, int n){
int ans = 0;
for(int pas = 1 << 16; pas > 0; pas /= 2)
if(pas + ans <= n && v[pas + ans].dr <= x)
ans += pas;
return ans;
}
int main()
{
int n;
fi >> n;
for(int i = 1; i <= n; i++)
fi >> v[i].st >> v[i].dr;
sort(v + 1, v + 1 + n, cmp);
for(int i = 1; i <= n; i++)
d[i] = max(d[i - 1], d[CB(v[i].st, n)] + v[i].dr - v[i].st);
fo << d[n];
fi.close();
fo.close();
return 0;
}