Cod sursă (job #732636)

#include <iostream>
#include <fstream>
#include <algorithm>
#include <set>


#pragma GCC optimize("O3")

using namespace std;
ifstream fin ("stampile.in");
ofstream fout ("stampile.out");
typedef long long ll;
const ll Nmax=2e5+5, inf=1e9+5;

ll n, m, v[Nmax];
struct ghiseu{
    ll l, r, v;
}g[Nmax];

bool cmp(ghiseu a, ghiseu b){
    return a.l<b.l;
}
struct CMP{
    bool operator()(ll a, ll b){
        return g[a].r>g[b].r;
    }
};
multiset <ll, CMP> st;
ll aib[Nmax];
void aib_update(ll pos, ll val){
    for (ll i=1; i<=n; i+=i&-i)
        aib[i]+=val;
    pos++;
    for (ll i=pos; i<=n; i+=i&-i)
        aib[i]-=val;
}
ll aib_querry(ll pos){
    ll sol=0;
    for (ll i=pos; i>0; i-=i&-i)
        sol+=aib[i];
    return sol;
}
int main()
{
    fin>>n>>m;
    for (ll i=1; i<=n; i++)
        fin>>v[i];
    for (ll i=0; i<m; i++)
        fin>>g[i].l>>g[i].r>>g[i].v;
    sort(g, g+m, cmp);
    ll crt=0, sol=0;
    bool ok=1;
    for (ll i=1; i<=n && ok; i++){
        while (crt<n && g[crt].l==i)
            st.insert(crt++);
        v[i]-=aib_querry(i);
        while (!st.empty() && v[i]>0 && g[*st.begin()].l<=i){
            ll ind=*st.begin();
            if (g[*st.begin()].r<i)
                st.erase(st.begin());
            else if (g[ind].v>v[i]){
                aib_update(g[ind].r, v[i]);
                g[ind].v-=v[i];
                sol+=v[i];
                v[i]=0;
            }
            else{
                aib_update(g[ind].r, g[ind].v);
                v[i]-=g[ind].v;
                sol+=g[ind].v;
                g[ind].v=0;
                st.erase(st.begin());
            }
        }
        if (v[i]>0)
            ok=0;
    }
    if (!ok)
        fout<<"-1";
    else fout<<sol;
    return 0;
}