Cod sursa(job #2809442)

Utilizator TghicaGhica Tudor Tghica Data 27 noiembrie 2021 00:14:36
Problema Lupul Urias si Rau Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.12 kb
#include <fstream>
#include <algorithm>

using namespace std;

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


int hp[131073], hindex[131073], valindex[100001], lastPoz;

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;

    aux = hindex[poz / 2];
    hindex[poz / 2] = hindex[poz];
    hindex[poz] = aux;

    aux = valindex[hindex[poz / 2]];
    valindex[hindex[poz / 2]] = valindex[hindex[poz]];
    valindex[hindex[poz]] = aux;

    poz /= 2;
  }
}

void downHeap(int poz) {
  int aux, path = 1;
  while (path && (hp[poz * 2] > hp[poz] or hp[poz * 2 + 1] > hp[poz])) {

    path = 0;

    if (poz * 2 <= lastPoz && hp[poz * 2] > hp[poz])///Arata groaznic, dar... atat s-a putut
      path = 1;
    if (poz * 2 + 1 <= lastPoz && hp[poz * 2 + 1] > hp[poz]) {
      path = 2;
      if (poz * 2 <= lastPoz && hp[poz * 2] > hp[poz] && hp[poz * 2] > hp[poz * 2 + 1])
        path = 1;
    }

    if (path == 1) {
      aux = hp[poz * 2];
      hp[poz * 2] = hp[poz];
      hp[poz] = aux;

      aux = hindex[poz * 2];
      hindex[poz * 2] = hindex[poz];
      hindex[poz] = aux;

      aux = valindex[hindex[poz * 2]];
      valindex[hindex[poz * 2]] = valindex[hindex[poz]];
      valindex[hindex[poz]] = aux;

      poz *= 2;
    }
    else if (path == 2) {
      aux = hp[poz * 2 + 1];
      hp[poz * 2 + 1] = hp[poz];
      hp[poz] = aux;

      aux = hindex[poz * 2 + 1];
      hindex[poz * 2 + 1] = hindex[poz];
      hindex[poz] = aux;

      aux = valindex[hindex[poz * 2 + 1]];
      valindex[hindex[poz * 2 + 1]] = valindex[hindex[poz]];
      valindex[hindex[poz]] = aux;

      poz *= 2;
      poz++;
    }
  }
}

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

void elimHeap(int elem) {
  int a, aux;

  a = valindex[elem];

  aux = hp[a];
  hp[a] = hp[lastPoz];
  hp[lastPoz] = aux;

  aux = hindex[a];
  hindex[a] = hindex[lastPoz];
  hindex[lastPoz] = aux;

  aux = valindex[hindex[a]];
  valindex[hindex[a]] = valindex[hindex[lastPoz]];
  valindex[hindex[lastPoz]] = aux;

  hp[valindex[elem]] = 0;
  hindex[valindex[elem]] = 0;
  valindex[elem] = 0;
  lastPoz--;
  downHeap(a);
}

int topHeap() {
  int rez = hp[1];
  elimHeap(hindex[1]);
  return rez;
}

int main() {
  ifstream cin("lupu.in");
  ofstream cout("lupu.out");
  int n, x, l, i, k;
  long long lung, sum, jump;
  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);
      k++;
    }
    sum += topHeap();
  }
  cout << sum;
  return 0;
}