Pagini recente » Cod sursa (job #554198) | Cod sursa (job #1732750) | Cod sursa (job #2254578) | Cod sursa (job #1572749) | Cod sursa (job #2541389)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
#define nmax 100001
int n, x, l, p, h[nmax], total;
inline int father(int nod) { return nod/2; }
inline int left_son(int nod) { return nod*2; }
inline int right_son(int nod) { return nod*2+1; }
struct oaie {
int dist, lana;
} a[nmax];
bool mycmp(oaie a, oaie b) {
return a.dist < b.dist;
}
void sift(int n, int nod) {
int son;
do {
son = 0;
if (left_son(nod) <= p) {
son = left_son(nod);
if (right_son(nod) <= p && h[right_son(nod)] > h[son])
son = right_son(nod);
if (h[son] <= h[nod]) son = 0;
}
if (son) {
swap(h[nod], h[son]);
nod = son;
}
} while (son);
}
void percolate(int n, int nod) {
int key = h[nod];
while (nod > 1 && key > h[father(nod)]) {
h[nod] = h[father(nod)];
nod = father(nod);
}
h[nod] = key;
}
void cut(int &p, int nod) {
h[nod] = h[p];
--p;
if (nod > 1 && h[nod] > h[father(nod)]) percolate(p,nod);
else sift(p,nod);
}
int main()
{
f >> n >> x >> l;
for (int i = 1; i <= n; ++i) f >> a[i].dist >> a[i].lana;
sort(a+1, a+n+1, mycmp);
/*for (int i = 1; i <= n; ++i) {
g << a[i].dist << ' ' << a[i].lana << '\n';
}*/
int j = 1;
int i = 0;
for (int i = 0; i - l < x ; i += l) {
while (a[j].dist <= i && j <= n)
if (a[j].dist <= x)
{
h[++p] = a[j].lana;
percolate(p,p);
++j;
}
else break;
total += h[1];
cut(p,1);
}
g << total << '\n';
return 0;
}