Cod sursa(job #2547576)

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

using namespace std;

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

const int dim = 100005;

int n;
pair <int,int> v[dim];

int heap[dim],len;

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

void Urca(int p)
{
    while (p > 1 && heap[p/2] < heap[p])
    {
        Schimba(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)
    {
        Schimba(p,bun);
        Coboara(bun);
    }
}

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

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

int main()
{
    in >> n;
    for (int i=1; i<=n; i++)
    {
        in >> v[i].first >> v[i].second;
    }
    sort(v+1,v+n+1);
    int j = n;
    for (int i=v[n].first; i>=1; i--)
    {
        while (j >= 1 && v[j].first >= i)
        {
            Adauga(v[j].second);
            j--;
        }
        if (len >= 1)
            Sterge();
    }
    long long int s = 0;
    while (len >= 1)
    {
        s += heap[1];
        Sterge();
    }
    out << s;
    return 0;
}