Pagini recente » Cod sursa (job #3000549) | Cod sursa (job #1516706) | Cod sursa (job #3230203) | Cod sursa (job #267179) | Cod sursa (job #2482608)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
const int N = 1000005;
pair < int, int > a[N];
int f[N], dad[N];
void usain_bolt()
{
ios::sync_with_stdio(false);
fin.tie(0);
}
int bs(int k)
{
int sol = -1;
int st = 1, dr = f[N - 1];
while(st <= dr) {
int mid = (st + dr) >> 1;
if(k >= a[f[mid]].second) {
if(sol == -1) sol = mid;
else {
sol = max(sol, mid);
}
st = mid + 1;
}
else dr = mid - 1;
}
return sol;
}
void path(int k, int & ans)
{
if(dad[k]) path(dad[k], ans);
ans += a[k].second - a[k].first;
}
int main()
{
usain_bolt();
int n;
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> a[i].first >> a[i].second;
sort(a + 1, a + 1 + n);
f[++f[N - 1]] = 1;
for(int i = 2; i <= n; ++i) {
int pos = bs(a[i].first);
if(pos != -1) {
dad[i] = f[pos];
f[pos + 1] = i;
f[N - 1] = max(f[N - 1], pos + 1);
}
}
int ans = 0;
for(int i = 1; i <= n; ++i) {
int cnt = 0;
path(i, cnt);
ans = max(ans, cnt);
}
fout << ans;
return 0;
}