简析
很显然这是一道差分+二分答案的题但我偏不这么写线段树的裸题。裸到什么程度呢？你需要实现一颗支持如下操作的线段树：
-
递归建树，自底向上（不然你要执行n次add操作吗？慢死你）
-
区间修改（这个不用说，把预约了的教室数量减掉）
-
查询区间最小值（一旦这个最小值小于0，则判断不满足题意）
值得注意的是，由于是查询区间最小值，所以在初始化时应当将线段树节点所存的值设为无穷大，并很显然地将 (pushup) 操作改为取左右子树的较小值即可。同时，在每次 (pushup) 操作完毕之后，检查一下当前节点值是否小于 (0)，使用一个全局 (bool) 变量 (flag) 记录是否满足条件，如果不满足，将 (flag) 归零并及时结束所有操作直接按题意输出当前的预约编号即可（对于单组数据节省时间的办法）。
由于线段树常数比较大，实测第十三个测试点会被卡，加个快读就能过了，可以说是非常水蓝的题了。
AC代码
#include<iostream>
#include<cstdio>
#include<cctype>
using namespace std;
const int inf = (1<<31)-1;
int read(){
int re = 0,ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) re = (re<<1) + (re<<3) + ch - '0',ch = getchar();
return re;
}
struct node{
int l,r,sum,add;
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define add(x) t[x].add
#define mid(x) (t[x].l + t[x].r >> 1)
}t[4000006];
bool flag = 1;
int num[1000006];
void check(int x){
if(sum(x) < 0) flag = 0;
//cout << "Now node is" << l(x) << ' ' << r(x) << endl << "Val is" << sum(x) << endl << endl;
}
void pushup(int x){
sum(x) = min(sum(x<<1),sum(x<<1|1));
}
void pushdown(int x){
if(add(x)){
sum(x<<1) -= add(x);
sum(x<<1|1) -= add(x);
add(x<<1) += add(x);
add(x<<1|1) += add(x);
add(x) = 0;
}
}
void build(int x,int l,int r){
l(x) = l;
r(x) = r;
add(x) = 0;
sum(x) = inf;
if(l == r){
sum(x) = num[l];
return;
}
build(x<<1,l,mid(x));
build(x<<1|1,mid(x) + 1,r);
pushup(x);
//cout << "Now node is" << l(x) << ' ' << r(x) << endl << "Val is" << sum(x) << endl << endl;
}
void addnum(int x,int l,int r,int v){
if(!flag) return;
if(l <= l(x) && r >= r(x)){
add(x) += v;
sum(x) -= v;
return;
}
pushdown(x);
if(l <= mid(x)) addnum(x<<1,l,r,v);
if(r > mid(x)) addnum(x<<1|1,l,r,v);
pushup(x);
check(x);
}
int n,m;
int main(){
n = read(),m = read();
for(int i = 1;i <= n;i++) num[i] = read();
build(1,1,n);
for(int i = 1;i <= m;i++){
int d = read(),s = read(),t = read();
flag = 1;
addnum(1,s,t,d);
if(!flag){
printf("-1
%d",i);
return 0;
}
}
printf("0
");
return 0;
}