Cod sursă (job #735734)

#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e5+2;
int n,m,a[NMAX],l,r,v;

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

struct BIT{
    int n;
    vector<int> aib;

    BIT(int _n){
        n = _n;
        aib.resize(n+1);
    }

    void update(int pos, int val){
        for(int i = pos; i <= n; i += (i&-i)){
            aib[i] += val;
        }
    }

    int query(int pos){
        int ans = 0;
        for(int i = pos; i > 0; i -= (i&-i)){
            ans += aib[i];
        }
        return ans;
    }
};

struct Range {
    int first, second;

    bool operator < (const Range &aux) const {
        return (second < aux.second) || (second == aux.second && first < aux.first);
    }

};
vector<Range> interv[NMAX];

int main()
{
    fin >> n >> m;
    BIT aib(n);
    for(int i = 1; i <= n; i++){
        fin >> a[i];
        aib.update(i, a[i]-a[i-1]);
    }

    for(int i = 1; i <= m; i++){
        fin >> l >> r >> v;
        interv[r].push_back({l, v});
    }
    set<Range> s;
    int ans = 0;
    for(int i = n; i >= 1; i--){
        for(auto it: interv[i]){
            s.insert(it);
        }
        a[i] = aib.query(i);
        while(a[i] > 0){
            auto it = *s.begin();
            s.erase(s.begin());
            int scad = min(a[i], it.second);
            aib.update(it.first, -scad);
            a[i] -= scad;
            ans += scad;
            it.second -= scad;
            if(it.second != 0){
                s.insert(it);
            }
            if(s.size() == 0){
                break;
            }
        }
        if(a[i] > 0){
            fout << "-1\n";
            return 0;
        }
    }
    fout << ans;
    return 0;
}