Pagini recente » Cod sursa (job #1778397) | Cod sursa (job #1493252) | Cod sursa (job #1044715) | Cod sursa (job #2977744) | Cod sursa (job #2397987)
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define maxn 100000
//#define aaa system("pause");
using namespace std;
pii v[maxn+5]; int dst[maxn+5];
int dp[maxn+5]; ///dp[i]-timp maxim cu bandele 0..i
bool cmp ( pii a, pii b )
{
if ( a.se != b.se ) return a.se < b.se;
return a.fi < b.fi;
}
int main ()
{
ifstream fin ( "heavymetal.in" );
ofstream fout ( "heavymetal.out" );
int n, i, j, pas;
fin >> n;
for ( i = 0; i < n; i++ ) fin >> v[i].fi >> v[i].se, v[i].se--;
sort ( v, v + n, cmp );
for ( i = 0; i < n; i++ ) dst[i] = v[i].se - v[i].fi + 1;
dp[0] = dst[0];
for ( i = 1; i < n; i++ )
{
dp[i] = dp[i-1];
for ( j = -1, pas = (1<<20); pas > 0; pas/=2 )
if ( j + pas <= i && v[j+pas].se < v[i].fi ) j += pas;
if ( j >= 0 ) dp[i] = dp[j] + dst[i];
}
fout << dp[n-1];
fin.close ();
fout.close ();
return 0;
}