题解 | 【入门班】借教室

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;

int n,m,r[N];
int d[N],s[N],t[N];

bool check(int mid){
	vector<int> diff(n+2,0);
	for(int i=1;i<=mid;i++){
		diff[s[i]]+=d[i];
		diff[t[i]+1]-=d[i];
	}
	int need=0;
	for(int i=1;i<=n;i++){
		need+=diff[i];
		if(need>r[i]){
			return false;
		}
	}
	return true;
}

void solve(){
	
	int l=1,r=m,mid;
	int res=0;
	
	while(l<=r){
		mid=l+r>>1;
		if(check(mid)){
			l=mid+1;
			res=mid;
		}else{
			r=mid-1;
		}
	}
	if(res==m){
		cout<<0<<endl;
	}else{
		cout<<res+1<<endl;
	}
	return;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>r[i];
	}
	
	for(int i=1;i<=m;i++){
		cin>>d[i]>>s[i]>>t[i];
	}
	
	solve();

    return 0;
}