Cod sursa(job #2541389)

Utilizator eduardcadarCadar Eduard eduardcadar Data 8 februarie 2020 13:10:22
Problema Lupul Urias si Rau Scor 68
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#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;
}