Cod sursa(job #2398233)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 5 aprilie 2019 10:55:07
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>
#define maxn 100000
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;

int dp[maxn+5], dst[maxn+5];
pii v[maxn+5];

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] = max(dp[i-1], dst[i]);
    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 && dst[i] + dp[j] > dp[i] ) dp[i] = dst[i] + dp[j];
  }
  fout << dp[n-1] << '\n';

  fin.close ();
  fout.close ();

  return 0;
}