Cod sursa(job #2547579)

Utilizator StanCatalinStanCatalin StanCatalin Data 15 februarie 2020 14:38:01
Problema Lupul Urias si Rau Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int dim = 100005;

int n,x,l,t[dim];
pair <long long int,long long int> a[dim];

long long int heap[dim],len = 0;

void Schimb(int p,int q)
{
    swap(heap[p], heap[q]);
}

void Urca(int p)
{
    while (p > 1 && heap[p] > heap[p/2])
    {
        Schimb(p,p/2);
        p /= 2;
    }
}

void Coboara(int p)
{
    int bun = p,fs = 2*p, fd = 2*p+1;
    if (fs <= len && heap[fs] > heap[bun])
    {
        bun = fs;
    }
    if (fd <= len && heap[fd] > heap[bun])
    {
        bun = fd;
    }
    if (bun != p)
    {
        Schimb(p,bun);
        Coboara(bun);
    }
}

void Adauga(long long int nr)
{
    heap[++len] = nr;
    Urca(len);
}

void Sterge()
{
    Schimb(1 ,len--);
    Coboara(1);
}

int main()
{
    in >> n >> x >> l;
    int m = 1;
    long long int maxi = -1;
    for (int i=1,x1,y; i<=n; i++)
    {
        in >> x1 >> y;
        if (x1 <= x)
        {
            a[m].first = (x - x1) / l + 1;
            a[m].second = y;
            m++;
            maxi = max(maxi , a[m-1].first);
        }
    }
    sort(a+1,a+m+1);
    long long int s = 0;
    int j = m;
    for (int i=maxi; i>=1; i--)
    {
        while (j > 0 && a[j].first == i)
        {
            Adauga(a[j].second);
            j--;
        }
        s += heap[1];
        if (len >= 1)
        {
            Sterge();
        }
    }
    out << s;
    return 0;
}