Cod sursă (job #785626)

#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int Nmax = 200005;

struct ghiseu{
    int utilizari, pagina_sfarsit;
};

int n, m, sol;
int stampile_necesare[Nmax];
int stampile_din_urma[Nmax];
vector<ghiseu> ghisee[Nmax];
priority_queue<pair<int, int>> ghisee_active;

void citire(){
    int pagina_inceput;
    ghiseu curent;

    fin >> n >> m;

    for(int i = 1; i <= n; i++){
        fin >> stampile_necesare[i];
    }

    for(int i = 1; i <= m; i++){
        fin >> pagina_inceput >> curent.pagina_sfarsit >> curent.utilizari;
        ghisee[pagina_inceput].push_back(curent);
    }
}

void utilizare_convenabil_ghisee(){
    int vizite;
    ghiseu gh;

    sol = 0;
    stampile_din_urma[0] = 0;

    for(int i = 1; i <= n && sol != -1; i++){
        while(!ghisee[i].empty()){
            gh = ghisee[i][ghisee[i].size() - 1];
            ghisee[i].pop_back();

            ghisee_active.push({gh.pagina_sfarsit, gh.utilizari});
        }

        stampile_din_urma[i] += stampile_din_urma[i - 1];
        stampile_necesare[i] -= stampile_din_urma[i];

        while(stampile_necesare[i] != 0 && !ghisee_active.empty()){
            gh.pagina_sfarsit = ghisee_active.top().first;
            gh.utilizari = ghisee_active.top().second;
            ghisee_active.pop();

            if(gh.pagina_sfarsit < i){
                continue;
            }

            vizite = min(stampile_necesare[i], gh.utilizari);

            stampile_din_urma[i] += vizite;
            stampile_din_urma[gh.pagina_sfarsit + 1] -= vizite;

            sol += vizite;
            stampile_necesare[i] -= vizite;
            gh.utilizari -= vizite;

            if(gh.utilizari > 0){
                ghisee_active.push({gh.pagina_sfarsit, gh.utilizari});
            }
        }

        if(ghisee_active.empty() && stampile_necesare[i] > 0){
            sol = -1;
        }
    }
}

void afisare_solutie(){
    fout << sol;
}

int main(){
    citire();

    utilizare_convenabil_ghisee();
    afisare_solutie();

    return 0;
}