这个难度感觉并没有那么高，因为这个题暴力也好打，但是比较难想出正解，因为如果你不看标签是很难想到这个题竟然是二分，当然前缀和应该很好想，毕竟让你求的是在某段时间内借教室的和是否满足。
这样我们可以很容易的推出借的教室的个数和订单是成正对应的，因此他可以满足单调性，所以我们就可以用上二分。
而原题中我们可以把天数看成x轴上的横坐标，这天的借教室数可以看成y轴上的纵坐标，而每一次订单的增加，我们就要让从第一个订单到这个订单中的所有订单都加起来，这就像一个区间修改，然后我们在判断的时候就需要用到单点查询这天满不满足。
因此我们可以想到差分数组和前缀和的结合，然后再搭配二分，就ok了。
代码：
// luogu-judger-enable-o2
#include<iostream>
#include<cstring>
#include<cstdio>
#define M 1000010
using namespace std;
struct cym {
int l ,r, d;
} e[M];
int delta[M], sum[M], nul[M], n, m;
bool flag;
bool check(int x) {
memset(delta, , sizeof(delta));
for(int i = ; i <= x; i++) {
delta[e[i].l] += e[i].d;
delta[e[i].r + ] -= e[i].d;
}
for(int i = ; i <= n; i++) {
sum[i] = sum[i - ] + delta[i];
if(sum[i] > nul[i])
return false;
}
return true;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++)
scanf ("%d", &nul[i]);
for (int i = ; i <= m; i++)
scanf ("%d%d%d", &e[i].d, &e[i].l, &e[i].r);
for(int i = ; i <= m; i++) {
delta[e[i].l] += e[i].d;
delta[e[i].r + ] -= e[i].d;
}
for(int i = ; i <= n; i++) {
sum[i] = sum[i - ] + delta[i];
if(sum[i] > nul[i])
flag = ;
}
if(!flag)
{
printf("");
return ;
}
int left = , right = m;
while (left < right) {
int mid = (left+right) / ;
if (check(mid))
left = mid + ;
else
right = mid;
}
printf ("-1\n%d", left);
}