Pagini recente » Cod sursa (job #122697) | Cod sursa (job #1017636) | Cod sursa (job #662833) | Cod sursa (job #1824538) | Cod sursa (job #2641492)
#include <bits/stdc++.h>
#define MAX 100001
using namespace std;
struct Interval
{
int in;
int sf;
int l;
}v[MAX];
bool cmp(Interval a, Interval b)
{
if(a.sf < b.sf)
return true;
if(a.sf == b.sf && a.in < b.in)
return true;
return false;
}
int main()
{
int n;
int answer = 0;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
fin >> n;
for(int i = 0; i < n; i++)
fin >> v[i].in >> v[i].sf;
sort(v, v + n, cmp);
for(int i = 0; i < n; i++)
{
int st = 0, dr = i - 1;
while(st <= dr)
{
int mij = (st + dr) >> 1;
if(v[mij].sf <= v[i].in)
st = mij + 1;
else
dr = mij - 1;
}
v[i].l = v[i].sf - v[i].in;
if(dr != -1)v[i].l += v[dr].l;
v[i].l = max(v[i].l, v[i - 1].l);
answer = max(answer, v[i].l);
}
fout << answer;
return 0;
}