Cod sursă (job #769039)

#include <bits/stdc++.h>
#define NMAX 200000
#define MOD 1000003
#define ll long long

using namespace std;

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

int n,q;
vector<int> lazy1[4*NMAX+1], aint1[4*NMAX+1];
int lazy2[4*NMAX+1], aint2[4*NMAX+1];

int  v[NMAX+1],s[NMAX+1];
pair<int,int> t[NMAX+1];


vector<int> combine(vector<int> x,vector<int> y)
{
    vector<int> c;
    int i=0,j=0;
    while(i < x.size() && j<y.size())
    {
        if(x[i]==y[j])
        {
            c.push_back(x[i]);
            i++;
            j++;
        }
        else if(x[i] < y[i])
        {
            c.push_back(x[i++]);
        }
        else
        {
            c.push_back(y[j++]);
        }
    }
    while(i < x.size())
    {
        c.push_back(x[i++]);
    }
    while(j < y.size())
    {
        c.push_back(y[j++]);
    }
    return c;
}
void propag1(int i)
{
    for(int j : lazy1[i])
    {
        lazy1[2*i].push_back(j);
        lazy1[2*i+1].push_back(j);

        aint1[2*i].push_back(j);
        aint1[2*i+1].push_back(j);
    }
    while(!lazy1[i].empty())
    {
        lazy1[i].pop_back();
    }
}
void update1(int i,int st,int dr,int l,int r,int x)
{
    if(l<=st && dr<=r)
    {
        lazy1[i].push_back(x);
        aint1[i].push_back(x);
    }
    else
    {
        propag1(i);
        int m = (st+dr)/2;
        if(l<=m)
        {
            update1(2*i,st,m,l,r,x);
        }
        if(m+1<=r)
        {
            update1(2*i+1,m+1,dr,l,r,x);
        }
        aint1[i] = combine(aint1[2*i],aint1[2*i+1]);
    }
}
vector<int> query1(int i,int st,int dr,int p)
{
    if(st==dr)
    {
        return aint1[i];
    }
    else
    {
        propag1(i);
        int m = (st+dr)/2;
        if(p<=m)
        {
            return query1(2*i,st,m,p);
        }
        else
        {
            return query1(2*i+1,m+1,dr,p);
        }
        aint1[i] = combine(aint1[2*i],aint1[2*i+1]);
    }
}
bool cmp(int x,int y)
{
    return t[x].first < t[y].first;
}
void propag2(int i)
{
    if(lazy2[i])
    {
        aint2[2*i]+=lazy2[i];
        aint2[2*i+1]+=lazy2[i];

        lazy2[2*i]+=lazy2[i];
        lazy2[2*i+1]+=lazy2[i];

        lazy2[i]=0;
    }
}

void update2(int i,int st,int dr,int l,int r,int x)
{
    if(l<=st && dr<=r)
    {
        lazy2[i] +=x;
        aint2[i] += x;
    }
    else
    {
        propag2(i);
        int m = (st+dr)/2;
        if(l<=m)
        {
            update2(2*i,st,m,l,r,x);
        }
        if(m+1<=r)
        {
            update2(2*i+1,m+1,dr,l,r,x);
        }
        aint2[i]=aint2[2*i]+aint2[2*i+1];
    }
}
int query2(int i,int st,int dr,int p)
{
    if(st==dr)
    {
        return aint2[i];
    }
    else
    {
        propag2(i);
        int m = (st+dr)/2;
        if(p<=m)
        {
            return query2(2*i,st,m,p);
        }
        else
        {
            return query2(2*i+1,m+1,dr,p);
        }

        aint2[i] = aint2[2*i] + aint2[2*i+1];
    }
}

int main()
{
    fin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        fin >> s[i];
    }
    for(int i=1;i<=q;i++)
    {
        fin >> t[i].first >> t[i].second >> v[i];

    }


    for(int i=1;i<=q;i++)
    {
        update1(1,1,n,t[i].first,t[i].second,i);
    }

    int res=0;
    for(int i=n;i>=1 && res >= 0;i--)
    {
        vector<int> r = query1(1,1,n,i);
        int val = query2(1,1,n,i);
        sort(r.begin(),r.end(),cmp);
        for(int j : r)
        {
            while(v[j] && val < s[i])
            {
                ++val;
                ++res;
                update2(1,1,n,t[j].first,t[j].second,1);
                v[j]--;
            }
        }
        if(val<s[i])
        {
            res = -1;
        }
    }
    fout << res;
}