Cod sursa(job #2638357)

Utilizator euyoTukanul euyo Data 27 iulie 2020 22:26:09
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin( "heavymetal.in" );
ofstream fout( "heavymetal.out" );

const int MaxN = 100001;

struct interval {
  int st, dr;
};

int tree[4 * MaxN + 1], ind[MaxN];
interval w[MaxN], v[MaxN];

int cautbin( int e, int n ) { //cea mai mare <= decat e
  int step, ind = 0;
 
  for ( step = 1; step <= n; step <<= 1 );
  for ( ; step > 0; step >>= 1 ) {
    if ( ind + step <= n ) {
      if ( v[ind + step].dr <= e ) {
        ind += step;
      }
    }
  }
  return ind;
}

void update( int node, int st, int dr, int pos, int val ) {
  int mij;
 
  if ( st == dr ) {
    tree[node] += val;
  } else {
    mij = (st + dr) / 2;
    if ( pos <= mij ) {
      update( 2 * node, st, mij, pos, val );
    } else {
      update( 2 * node + 1, mij + 1, dr, pos, val );
    }
    tree[node] = max( tree[2 * node], tree[2 * node + 1] );
  }
}
int query( int node, int st, int dr, int a, int b ) {
  int mij, x = 0, y = 0;
 
  if ( a <= st && dr <= b ) {
    return tree[node];
  }
  mij = (st + dr) / 2;
  if ( a <= mij ) {
    x = query( 2 * node, st, mij, a, b );
  }
  if ( b > mij ) {
    y = query( 2 * node + 1, mij + 1, dr, a, b );
  }
  return max( x, y );
}

int cmp( int a, int b ) {
  return w[a].st < w[b].st;
}

int main() {
  int n, i, p;
  
  fin >> n;
  for ( i = 1; i <= n; ++i ) {
    fin >> w[i].st >> w[i].dr;
    ind[i] = i;  
  }
  sort( ind + 1, ind + n + 1, cmp );
  for ( i = 1; i <= n; ++i ) {
	v[i].st = w[ind[i]].st;
	v[i].dr = w[ind[i]].dr;
	//printf( "%d %d\n", v[i].st, v[i].dr );
  }
  update( 1, 1, n, 1, v[1].dr - v[1].st );  
  for ( i = 2; i <= n; ++i ) {
	p = cautbin( v[i].st, i - 1 );
	//printf( "%d %d\n", p, v[i].st );
    update( 1, 1, n, i, query( 1, 1, n, 1, p ) + v[i].dr - v[i].st );
  }
  fout << query( 1, 1, n, 1, n );
  fin.close();
  fout.close();
  return 0;
}