思路

存在不能满足的订单，也就是存在某一天需要的教室数量大于可用于租借的教室数量。
容易发现，如果到第 $X$ 个订单时存在某天教室不够，那到第 $X+1\sim n$ 肯定都会存在某天教室数量不够。
所以可以二分订单，并判断从第 $1$ 个订单到这个订单是不是都能满足。
对于每次判断，形式都是有一段区间加同一个数，并判断最终结果是否有哪天数字大于 $r_i$。
容易发现，这个区间加和最后一次查询可以通过差分修改和前缀和统计来完成。

时间复杂度为 $O(n\log m)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;

int n,m;
int r[1000003];
int d[1000003];
pii a[1000003];
ll c[1000003];

bool check(int x){
	memset(c,0,sizeof(c));
	for(int i=1;i<=x;i++){
		c[a[i].first]+=d[i];
		c[a[i].second+1]-=d[i];
	}
	for(int i=1;i<=n;i++){
		c[i]+=c[i-1];
		if(c[i]>r[i])return 0;
	}
	return 1;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.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]>>a[i].first>>a[i].second;
	}
	int lft=1,rig=m,mid,ans=-1;
	while(lft<=rig){
		mid=lft+rig>>1;
		if(check(mid))lft=mid+1;
		else{
			ans=mid;
			rig=mid-1;
		}
	}
	if(ans==-1)cout<<0;
	else cout<<"-1\n"<<ans;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int n, m;
LL b[N], c[N], L[N], R[N], a[N], d[N];
bool check(int x)
{
    memset(d, 0, sizeof(d));
    for(int i=1; i<=x; i++)
    {
        d[L[i]] += c[i];
        d[R[i]+1] -= c[i]; 
    }
    for(int i=1; i<=n; i++)
    {
        a[i] = a[i-1] + d[i];
        if(a[i] > b[i]) return 0;
    }
    return 1;
} 
int main()
{ 
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%lld", &b[i]);
    for(int i=1; i<=m; i++) scanf("%lld%lld%lld", &c[i], &L[i], &R[i]);
    if(check(m)){printf("0\n"); return 0;}
    int l=1, r=n, ans=0;
    while(l <= r)
    {
        int mid=(l+r)/2;
        if(check(mid)) l=mid+1, ans=mid;
        else r=mid-1;
    }
    printf("-1\n%d\n", ans+1);
    return 0;
}