Cod sursa(job #2809359)

Utilizator TghicaGhica Tudor Tghica Data 26 noiembrie 2021 19:11:07
Problema Lupul Urias si Rau Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <algorithm>

using namespace std;

struct oaie{
  int lana;
  long long dist;
}v[100001];

int hp[100001], lastPoz = 0;

bool cmp(oaie a, oaie b) {
  return a.dist < b.dist;
}

void upHeap(int poz) {
  int aux;
  while (poz != 1 && hp[poz / 2] < hp[poz]) {
    aux = hp[poz / 2];
    hp[poz / 2] = hp[poz];
    hp[poz] = aux;
    poz /= 2;
  }
  return;
}

void downHeap(int poz) {
  int aux;
  while (hp[poz * 2] > hp[poz] or hp[poz * 2 + 1] > hp[poz]) {
    if (hp[poz * 2] > hp[poz]) {
      aux = hp[poz * 2];
      hp[poz * 2] = hp[poz];
      hp[poz] = aux;
      poz *= 2;
    } else if(hp[poz * 2 + 1] > hp[poz]) {
      aux = hp[poz * 2 + 1];
      hp[poz * 2 + 1] = hp[poz];
      hp[poz] = aux;
      poz *= 2;
      poz++;
    }
  }
  return;
}

void addHeap(int val) {
  lastPoz++;
  hp[lastPoz] = val;
  upHeap(lastPoz);
}

int topHeap() {
  int rez = hp[1];
  hp[1] = hp[lastPoz];
  lastPoz--;
  downHeap(1);
  return rez;
}

int main() {
  ifstream cin("lupu.in");
  ofstream cout("lupu.out");
  int n, x, l, i, jump, lung, k;
  long long sum;
  cin >> n >> x >> l;
  for (i = 1; i <= n; i++) {
    cin >> v[i].dist >> v[i].lana;
  }
  sort(v + 1, v + n + 1, cmp);
  jump = (x - v[1].dist) / l;
  if ((x - v[1].dist) % l == 0)
    jump++;
  for (i = 1; i <= n; i++) {
    v[i].dist += (long long)jump * l;
  }
  lung = 0;
  k = 1;
  sum = 0;
  for (i = 1; i <= jump; i++) {
    lung += l;
    while ( k <= n && v[k].dist - lung <= x) {
      addHeap(v[k].lana);
      k++;
    }
    sum += topHeap();
  }
  cout << sum;
  return 0;
}