Miku

很简单的二分

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long n,m;
long long r[1000001];
long long d[1000001];
long long cha[1000001];
long long s[1000001];
long long t[1000001];
long long l;
bool check(long long x){
//  cout<<x<<" ";
    memset(cha,0,sizeof(cha));
    for(long long i=1;i<=x;++i){
        cha[s[i]]+=d[i];
        cha[t[i]+1]-=d[i];
    }
    long long sum=0;
    for(long long i=1;i<=n;++i){

        sum+=cha[i];
//      cout<<sum<<" ";
        if(sum>r[i])
        return 0;
    }
//  cout<<endl;
    return 1;
}
long long  ans=0x7fffff;
int main(){
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=n;++i){
        scanf("%lld",&r[i]);
    }
    for(long long i=1;i<=m;++i){
        scanf("%lld%lld%lld",&d[i],&s[i],&t[i]);      
    }
    long long r=m;
    if(check(m)){
    cout<<0; 
    return 0;
    }
    while(l<=r){
        long long mid=l+(r-l)/2;
        if(check(mid)){
            l=mid+1;
        }else{
        //  ans=min(ans,mid);
            r=mid-1;
        }
    }
    cout<<-1<<endl<<l;
    return 0;
}