Pagini recente » Profil PetreCatalin | Cod sursa (job #1504840) | Cod sursa (job #1799174) | Cod sursa (job #2273990) | Cod sursa (job #2299413)
#include <bits/stdc++.h>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
const int MAX = 1e5 + 5;
struct interval
{
int x, y, z;
};
interval r[MAX];
int n, t;
long long v[2 * MAX], p[2 * MAX], dp[2 * MAX];
inline bool cmp(interval &a, interval &b)
{
return a.y < b.y;
}
inline int BS(int x)
{
int r = 0;
for(int pas = 1 << 19; pas; pas >>= 1)
if(r + pas <= t && v[r + pas] <= x)
r += pas;
if(v[r] == x)
return r;
return 0;
}
void Read_Init()
{
f >> n;
for(int i = 1; i <= n; ++i)
{
f >> r[i].x >> r[i].y;
r[i].z = r[i].y - r[i].x;
v[++t] = r[i].x;
v[++t] = r[i].y;
}
sort(v + 1, v + t + 1);
for(int i = 1; i <= t; ++i)
if(v[i] != v[i - 1])
p[i] = p[i - 1] + 1;
else
p[i] = p[i - 1];
for(int i = 1; i <= n; ++i)
{
r[i].x = p[BS(r[i].x)];
r[i].y = p[BS(r[i].y)];
}
sort(r + 1, r + n + 1, cmp);
}
void DP()
{
int j = 1;
for(int i = 1; i <= t; ++i)
{
dp[i] = max(dp[i], dp[i - 1]);
while(j <= n && r[j].y < i)
++j;
while(j <= n && r[j].y == i)
{
dp[i] = max(dp[i], dp[r[j].x] + r[j].z);
++j;
}
}
g << dp[t] << "\n";
}
int main()
{
Read_Init();
DP();
return 0;
}