【题解】LuoGu1083：借教室

原题传送门
不能满足的方案满足二分性
二分枚举什么时候无法满足

然后$O(n)$用差分算出每天需要的教师数量进行判断

Code：

#include <bits/stdc++.h>
#define maxn 1000010
#define LL long long
using namespace std;
int n, m;
LL a[maxn], b[maxn], d[maxn], s[maxn], t[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool check(int mid){
	for (int i = 1; i <= n; ++i) a[i] = 0;
	for (int i = 1; i <= mid; ++i) a[s[i]] += d[i], a[t[i] + 1] -= d[i];
	for (int i = 1; i <= n; ++i)
		if ((a[i] += a[i - 1]) > b[i]) return 1;
	return 0;
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) b[i] = read();
	for (int i = 1; i <= m; ++i) d[i] = read(), s[i] = read(), t[i] = read();
	int l = 1, r = m, ans = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid - 1, ans = mid; else l = mid + 1;
	}
	if (ans > 0) printf("-1\n%d\n", ans);
	else printf("0");
	return 0;
}