Cod sursa(job #3142759)

Utilizator Ana_22Ana Petcu Ana_22 Data 24 iulie 2023 12:19:46
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define NMAX 100000

using namespace std;

struct str {
  int pasi, val;
} v[NMAX], heap[NMAX];
int nexxt[NMAX];
int heapsize, pas;

bool cmp( str a, str b ) {
  if( a.pasi != b.pasi )
    return a.pasi < b.pasi;
  return a.val < b.val;
}

inline int parent(int i) { return (i - 1) / 2; }
inline int leftChild(int i) { return i * 2 + 1; }
inline int rightChild(int i) { return i * 2 + 2; }

void first_del();

void upHeap(int i) {
  while (i && heap[parent(i)].val < heap[i].val) {
    swap(heap[parent(i)], heap[i]);
    i = parent(i);
  }
}

void downHeap(int i) {
  int left, right, biggest;

  biggest = i;
  left = leftChild(i), right = rightChild(i);

  if (left < heapsize && heap[left].val > heap[biggest].val)
    biggest = left;
  if (right < heapsize && heap[right].val > heap[biggest].val)
    biggest = right;

  if (i != biggest) {
    swap(heap[i], heap[biggest]);
    downHeap(biggest);
  }
}


void extractMax() {
  swap( heap[0], heap[--heapsize] );
  downHeap( 0 );
}

void heap_insert( str oaie ) {
  heap[heapsize++] = oaie;
  upHeap( heapsize - 1 );
}

void update(int i, int value) {
  heap[i].val = value;
  upHeap(i);
  downHeap(i);
}

int getMax() {
  return heap[0].val;
}

void heap_delete(int i) {
  update(i, getMax());
  extractMax();
}

void first_del() {
  while( heapsize && heap[0].pasi < pas )
    heap_delete( 0 );
}


int main() {
    FILE *fin, *fout;
    int n, x, l, i, d, a, pas_max, st, finn, j;
    long long sum;
    fin = fopen( "lupu.in", "r" );
    fout = fopen( "lupu.out", "w" );
    fscanf( fin, "%d%d%d", &n, &x, &l );
    pas_max = 0;
    sum = 0;
    for( i = 0; i < n; i++ ) {
      fscanf( fin, "%d%d", &d, &a );
      v[i].pasi = ( x - d + l ) / l;
      v[i].val = a;
      if( v[i].pasi > pas_max )
        pas_max = v[i].pasi;
    }
    sort( v, v + n, cmp );
    i = 0;
    for( pas = 1; pas <= pas_max; pas++ ) {
      while( v[i].pasi < pas )
        i++;
      if( v[i].pasi == pas ) {
        st = i;
        while( v[i].pasi == pas )
          i++;
        finn = i - 1;
        for( j = st; j <= finn - pas + 1; j++ )
          heap_insert( v[j] );
        nexxt[pas] = j;
      }
    }
    for( pas = 1; pas <= pas_max; pas++ ) {
      if( heapsize ) {
        first_del();
        sum += getMax();
        extractMax();
      }
      for( j = pas + 1; j <= pas_max; j++ ) {
        if( v[nexxt[j]].pasi == j ) {
          heap_insert( v[nexxt[j]] );
          nexxt[j]++;
        }
      }
    }
    fprintf( fout, "%lld", sum );
    fclose( fin );
    fclose( fout );
    return 0;
}