Cod sursa(job #2631948)

Utilizator euyoTukanul euyo Data 1 iulie 2020 16:53:52
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int MaxN = 100001;

int d[MaxN], l[MaxN], ind[MaxN];
long long t[MaxN], heap[MaxN];

int indH;
 
static inline int fth( int node ) {
  return (node >> 1);
}
static inline int lSon( int node ) { 
  return node << 1;
}
static inline int rSon( int node ) {
  return ((node << 1) + 1);
}
void swap( int a, int b ) {
  int aux;
 
  aux = heap[a];
  heap[a] = heap[b];
  heap[b] = aux;
}
void repairUpp( int node ) {
  while ( node > 1 && heap[node] > heap[fth( node )] ) {
	swap( node, fth( node ) );
	node = fth( node );
  }
}
void repairDown( int node ) { 
  int son;	
 
  while ( node < indH ) {
	if ( lSon( node ) <= indH && rSon( node ) <= indH ) {
      if ( heap[lSon( node )] > heap[rSon( node )] ) {
        son = lSon( node );
	  } else {
		son = rSon( node );
	  }
	} else if ( lSon( node ) > indH && rSon( node ) <= indH ) {
	  son = rSon( node );
	} else if ( rSon( node ) > indH && lSon( node ) <= indH ) {
	  son = lSon( node );
	} else {
	  son = indH + 1;
	}
    if ( son <= indH && heap[son] > heap[node] ) {
      if ( son <= indH ) {
		swap( son, node );
	    node = son;
	  } else {
		node = indH + 1;
	  }
	} else {
	  node = indH + 1;
	}	
  }
}
void add( long long value ) {
  ++indH;
  heap[indH] = value;
  repairUpp( indH );
}
void cutMax() {
  swap( indH, 1 );
  --indH;
  repairUpp( 1 );
  repairDown( 1 );
}

int cmp( int a, int b ) {
  return t[a] > t[b];
}

int main() {
  int n, range, dist, i;
  long long maxl;
  
  fin >> n >> range >> dist;
  for ( i = 0; i < n; ++i ) {
	fin >> d[i] >> l[i];
    t[i] = (range - d[i]) / dist + 1;
	ind[i] = i;
  }
  sort( ind, ind + n, cmp ); 
  maxl = 0;
  add( l[ind[0]] );  
  for ( i = 1; i < n; ++i ) {
	if ( t[ind[i]] < t[ind[i - 1]] ) {
      maxl += heap[1];
	  cutMax();
	}
	add( l[ind[i]] );
  }
  maxl += heap[1];
  fout << maxl;
  fin.close();
  fout.close();
  return 0;
}