9. 借教室 80

常规
1 
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1000010];
long long d[1000010],l[1000010],r[1000010],s[1000010];
bool check(long long mid){ 
	memset(s,0,1000010);
	for(long long i=1;i<=mid;i++){
		s[l[i]]+=d[i];
		s[r[i]+1]-=d[i];
	}
	for(long long i=1;i<=n;i++){
		s[i]+=s[i-1];
		if(s[i]>a[i]) return 0;
	}
	return 1;
}
int main(){
	cin>>n>>m;
	long long f=1;
	for(long long i=1;i<=n;i++) cin>>a[i];
	for(long long i=1;i<=m;i++) cin>>d[i]>>l[i]>>r[i];
	if(check(m)){
		cout<<"0";
		return 0;
	}
	long long l=0,r=m+1;
	while(l+1<r){
		long long mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	cout<<"-1"<<endl<<r;
 	return 0;
}
2

题目