Cod sursa(job #2785398)

Utilizator YusyBossFares Yusuf YusyBoss Data 18 octombrie 2021 17:15:18
Problema Lupul Urias si Rau Scor 96
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>
#include <algorithm>
#define NMAX 100000
#pragma optimize ("o3")

using namespace std;

ifstream cin ("lupu.in");
ofstream cout ("lupu.out");

struct hatz {
  int lana, repets;
};

int n;
int vaib[NMAX + 1];
bool vf[NMAX + 1];
hatz v[NMAX + 1];

bool cmp(hatz A, hatz B) {
  if (A.lana == B.lana)
    return A.repets > B.repets;
  return A.lana > B.lana;
}

static inline int lsb(int val) {
  return val & (-val);
}

void update(int poz, int val) {
  while (poz <= n) {
    vaib[poz] += val;
    poz += lsb(poz);
  }
}

int query1(int poz) { /// returneaza suma (1,poz)
  int sol = 0;
  while (poz > 0) {
    sol += vaib[poz];
    poz -= lsb(poz);
  }

  return sol;
}

int query2(int st, int dr) {
  int mij, sol;

  sol = -1;
  while (st <= dr) {
    mij = (st + dr) / 2;

    if (vf[mij] == 0)
      sol = mij;
    if (query1(dr) - query1(mij - 1) < dr - mij + 1)
      st = mij + 1;
    else {
      dr = mij - 1;
      if (sol > -1)
        return sol;
    }
  }

  return sol;
}

int getnr() {
  int nr;
  char ch;

  ch = cin.get();
  while (!(ch >= '0' && ch <= '9'))
    ch = cin.get();

  nr = 0;
  while (ch >= '0' && ch <= '9') {
    nr = nr * 10 + ch - '0';
    ch = cin.get();
  }

  return nr;
}

int main(){
  int x, l, i, a, poz;
  long long sol;
  cin >> n >> x >> l;

  for (i = 1; i <= n; ++i) {
    a = getnr();
    v[i].lana = getnr();

    if (v[i].lana >= (1LL << 25))
      return 1;

    if (x >= a)
      v[i].repets = (x - a) / l + 1;
    else
      v[i].repets = -1;
  }

  sort(v + 1, v + n + 1, cmp);

  sol = 0;
  for (i = 1; i <= n; i++) {
    if (v[i].repets > 0) {
      poz = query2(1, v[i].repets);
      if (poz > -1) {
        vf[poz] = 1;
        update(poz, 1);
        sol += v[i].lana;
      }
    }
  }

  cout << sol;
  return 0;
}