Cod sursa(job #1847678)

Utilizator ciprianprohozescuProhozescu Ciprian ciprianprohozescu Data 14 ianuarie 2017 21:01:55
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

struct oaie
{
    long long t, a;
};

long long nr, x, l, H[100010], s, n;
oaie o[100010];

void citire();
bool crit(oaie a, oaie b);
void rezolvare();
void inserare(long long x);
void combinare(long long i);
long long extrage_max();

int main()
{
    citire();
    rezolvare();
    fout << s << '\n';
    fout.close();
    return 0;
}

void citire()
{
    long long i, lg;
    fin >> nr >> x >> l;
    for (i = 1; i <= nr; i++)
    {
        fin >> lg >> o[i].a;
        if (x >= lg)
            o[i].t = (x - lg) / l + 1;
    }
    sort(o + 1, o + nr + 1, crit);
}
bool crit(oaie a, oaie b)
{
    return a.t >= b.t;
}
void rezolvare()
{
    long long i = 1, zi, j;
    zi = o[1].t;
    if (x > 0)
    {
        while (o[i].t == zi)
        {
            H[++n] = o[i].a;
            i++;
        }
        zi = o[i].t;
        for (j = n / 2; j > 0; j--)
            combinare(j);
        for (j = 1; j <= o[i - 1].t - zi && H[1]; j++)
            s += extrage_max();
        while (zi > 0)
        {
            while (o[i].t == zi)
            {
                inserare(o[i].a);
                i++;
            }
            for (j = 1; j <= zi - o[i].t && H[1]; j++)
                s += extrage_max();
            zi = o[i].t;
        }
    }
}
void inserare(long long x)
{
    long long fiu = ++n, tata = fiu / 2;
    while (tata && H[tata] < x)
    {
        H[fiu] = H[tata];
        fiu = tata;
        tata = fiu / 2;
    }
    H[fiu] = x;
}
void combinare(long long i)
{
    long long x = H[i], tata = i, fiu;
    while (true)
    {
        fiu = 2 * tata;
        if (fiu > n)
            break;
        if (fiu + 1 <= n && H[fiu + 1] > H[fiu])
            fiu++;
        if (H[fiu] <= x)
            break;
        H[tata] = H[fiu];
        tata = fiu;
    }
    H[tata] = x;
}
long long extrage_max()
{
    long long maxim = H[1];
    H[1] = H[n--];
    combinare(1);
    return maxim;
}