Pagini recente » Cod sursa (job #743500) | Cod sursa (job #3238043) | Cod sursa (job #1352567) | Cod sursa (job #407784) | Cod sursa (job #2815094)
#include <bits/stdc++.h>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct trupa
{
int st,dr,nrant = 0;
};
int n;
trupa a[100005];
int cb(int p)
{
int dr = n + 1,pas = 1 << 16;
while (pas != 0)
{
if (dr - pas >= 1 and dr - pas <= n and a[dr - pas].st >= p)
dr -= pas;
pas /= 2;
}
return dr;
}
int main()
{
in >> n;
for (int i = 1; i <= n; i++)
in >> a[i].st >> a[i].dr;
sort(a + 1,a + n + 1,[](trupa A,trupa B){
if (A.st != B.st)
return A.st < B.st;
return A.dr < B.dr;
});
for (int i = 1; i <= n; i++)
{
if (a[i].nrant < a[i - 1].nrant)
a[i].nrant = a[i - 1].nrant;
int pos = cb(a[i].dr);
a[pos].nrant = max(a[pos].nrant,a[i].nrant + a[i].dr - a[i].st);
}
int maxim = 0;
for (int i = 1; i <= n; i++)
if (a[i].dr - a[i].st + a[i].nrant > maxim)
maxim = a[i].dr - a[i].st + a[i].nrant;
out << maxim;
return 0;
}