Cod sursa(job #1498998)

Utilizator mirupetPetcan Miruna mirupet Data 9 octombrie 2015 23:55:10
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<cstdio>
#include<algorithm>
#define DIM 100001
using namespace std;

int N, X, L, NR, time;
int w[DIM + 1], Heap[DIM + 1];
long long sol;

void percolate(int);
void sift(int);

struct vec {int x, y;} v[DIM + 1];

inline bool comp(vec a, vec b)
{
    return a.x > b.x;
}

void change(int i, int j)
{
    int aux = Heap[i];
    Heap[i] = Heap[j];
    Heap[j] = aux;
}

int main()
    {
        freopen("lupu.in","r",stdin);
        freopen("lupu.out","w",stdout);

        int i;

        scanf("%d%d%d", &N, &X, &L);

        for (i = 1; i <= N; i++)
        {
            scanf("%d%d", &v[i].x, &v[i].y);
            w[i] = i;
        }

        sort(v + 1, v + N + 1, comp);

        for (i = 1; i <= N; i++)
        {
            if (X >= time * L + v[w[i]].x)
            {
                Heap[++NR] = v[w[i]].y;
                percolate(NR);
                time++;
            }
            else
            {
                if (Heap[1] < v[w[i]].y)
                {
                    Heap[1] = v[w[i]].y;
                    sift(1);
                }
            }
        }

        for (i = 1; i <= NR; i++)
            sol += Heap[i];

        printf("%ld", sol);

    }

void percolate(int i)
{
    while (i >= 2 && Heap[i] < Heap[i / 2])
    {
        change(i, i / 2);
        i = i / 2;
    }
}

void sift(int i)
{
    int fs = 2 * i , fd = 2 * i + 1 , good = i;

    if (2 * i <= NR && Heap[good] > Heap[2 * i])
        good = 2 * i;

    if (2 * i + 1 <= NR && Heap[good] > Heap[2 * i + 1])
        good = 2 * i + 1;

    if (good != i)
    {
        change(good, i);
        sift(good);
    }
}