Cod sursa(job #3144775)

Utilizator Eraserurares campean Eraseru Data 10 august 2023 16:43:10
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
pair <int, int> el[100002];
vector <int> g;
long long n, rmax, intv, sTot;
void adauga(int x) {
    g.push_back (x);
    int ic = g.size() - 1;
    while (ic / 2 > 0 && g[ic] > g[ic / 2]) {
        swap (g[ic], g[ic / 2]);
        ic /= 2;
    }
}

void elimina() {
    g[1] = g[g.size() - 1];
    g.pop_back();
    unsigned int ic = 1, icop = ic * 2;
    while (icop <= g.size() - 1) {
        icop = ic * 2;
        if (icop + 1 <= g.size() - 1 && g[icop] < g[icop + 1])
            icop++;
        if (icop < g.size() && g[ic] < g[icop]) {
            swap (g[ic], g[icop]);
            ic = icop;
        }
        else
            icop = g.size();
    }
}

int main() {
    g.push_back (0);
    fin >> n >> rmax >> intv;
    for (int i = 1; i <= n; i++) {
        fin >> el[i].first >> el[i].second;
        el[i].first = (el[i].first + intv - 1) / intv;
    }
    sort(el + 1, el + n + 1);
    int j = 1;
    for (int i = 0; i <= (rmax + intv - 1) / intv; i++){
        while (el[j].first <= i && j <= n)
            adauga (el[j++].second);
        if (g.size() - 1) {
            sTot += g[1];
            elimina();
        }
    }
    fout << sTot;
}