Pagini recente » Cod sursa (job #156177) | Cod sursa (job #2641461) | Cod sursa (job #651974) | Cod sursa (job #3140901) | Cod sursa (job #2809442)
#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;
}