Pagini recente » Cod sursa (job #913750) | Cod sursa (job #2939289) | Cod sursa (job #747504) | Cod sursa (job #3248270) | Cod sursa (job #2809363)
#include <fstream>
#include <algorithm>
using namespace std;
struct oaie{
int lana;
long long dist;
}v[100001];
int hp[131073], 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;
}
}
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++;
}
}
}
void addHeap(int val) {
lastPoz++;
hp[lastPoz] = val;
upHeap(lastPoz);
}
int topHeap() {
int rez = hp[1];
hp[1] = hp[lastPoz];
if( lastPoz != 0 )
lastPoz--;
downHeap(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++;
}
sum += topHeap();
}
cout << sum;
return 0;
}