华哥倒酒<区间标记，二分>

题目链接

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=400000+10;
int a[maxn],v[maxn],s[maxn],t[maxn];
LL sum[maxn];//标记区间
int n,m;
int check(int m)
{
    for(int i=0;i<=n;i++)
        sum[i]=0;
    for(int i=1;i<=m;i++)
    {
        sum[t[i]]+=v[i];
        sum[s[i]-1]-=v[i];
    }
    int add=0;
    for(int i=n;i>=1;i--)
    {
        add+=sum[i];
        if(add>a[i])
            return 1;
    }
    return 0;
}
int main ()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int j=1;j<=m;j++)
            scanf("%d%d%d",&v[j],&s[j],&t[j]);
        int l=1,r=m,fg=0,mid=0;
        while(l<r)
        {
            mid=(l+r)>>1;
            if(check(mid))
            {
                fg=1;
                r=mid;
            }
            else
                l=mid+1;
        }
        if(fg)
            printf("-1
%d
",l);
        else
            printf("0
");
    }
    return 0;
}