利用了差分，前缀和和二分

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
long long n,m,j[N+10],sh[N+10],st[N+10],ed[N+10],diff[N+10],pre[N+10];
bool fx(int x)//判断前x个申请是否无法满足
{
    memset(diff,0,sizeof(diff));
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=x;i++)//差分数组
    {
        diff[st[i]]+=sh[i];
        diff[ed[i]+1]-=sh[i];
    }
    for(int i=1;i<=n;i++)//计算n天的前缀和
    {
        pre[i]=pre[i-1]+diff[i];
        if(pre[i]>j[i])
        {
            return false;//如果出现无法满足就return false；
        }
    }
    return true;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>j[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>sh[i]>>st[i]>>ed[i];
    }
    if(fx(m))//先判断全部能否满足，不能再查找位置
    {
        cout<<0;
        return 0;
    }
    int l,r,mid,ans=1;//二分查找
    l=1;
    r=m;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(fx(mid))
        {
            l=mid+1;
            ans=mid+1;
        }
        else
        {
            r=mid-1;
        }
    }
    cout<<-1<<endl<<ans;
}