题解 | #【入门班】借教室#

#include<bits/stdc++.h>
using namespace std;
 int n,m;
const int N=1e6+9;
int a[N],c[N];
struct dd{
    int d,s,t;
}p[N];
bool ck(int x){//x为订单顺序
   memset(c,0,sizeof(c));
    for(int i=1;i<=x;i++)
    c[p[i].s]+=p[i].d,c[p[i].t+1]-=p[i].d;
    
    for(int i=1;i<=n;i++){
        c[i]+=c[i-1];
        if(c[i]>a[i])return 0;
    }

    return 1;
}
int main(){
   cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
   for(int i=1;i<=m;i++)cin>>p[i].d>>p[i].s>>p[i].t;
    int l=0,r=m+1;
    while(l+1!=r){
        int mid=(l+r)>>1;
        if(ck(mid))l=mid;
        else r=mid;
    }
    if(r>m)cout<<0;
    else cout<<r;
    
    
    return 0;
}