记录编号	193060	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	2.132 s
提交时间	2015-10-13 19:40:14	内存使用	19.37 MiB

/*用某一天的前缀和表示该天需要的教室数
比如一开始数列a是0 0 0 0 0 0
前缀和0 0 0 0 0 0
3到5天需要2的教室
将a[3]+=2,a[6]-=2
数列变为0 0 2 0 0 -2
前缀和变为0 0 2 2 2 0
这样就实现了增加3-5需要的教室数
然后我们二分订单数
处理前mid个订单看看是否有某一天的前缀和大于di*/
#include <cstdio>
#include <cctype>
#include <algorithm>
 
template <class T>
T qread(T &x){
	x = 0;
	char c;
	while (! isdigit(c = getchar()));
	while (isdigit(c)){
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x;
}
 
const int MAX(1000010);
inline bool ok(int);
int n, m, r[MAX], d[MAX], s[MAX], t[MAX], ans = 0, sum, ss[MAX];
 
main()
{
	freopen("classrooms.in", "r", stdin);
	freopen("classrooms.out", "w", stdout);
	qread(n);
	qread(m);
	for (int i = 1; i <= n; ++i)
		qread(r[i]);
	for (int i = 1; i <= m; ++i){
		qread(d[i]);
		qread(s[i]);
		qread(t[i]);
	}
	fclose(stdin);
	
	int ll = 1, rr = m;
	while (ll <= rr){
		int mid = (ll + rr) >> 1;
		if (! ok(mid)){
			ans = mid;
			rr = mid - 1;
		}
		else
			ll = mid + 1;
	}
	if (! ans)
		putchar('0');
	else
		printf("-1\n%d", ans);
}
 
inline bool ok(int x){
	std::fill(ss, ss + MAX, 0);
	sum = 0;
	for (int i = 1; i <= x; i++){
		ss[s[i]] += d[i];
		ss[t[i] + 1] -= d[i];
	}
	for (int i = 1; i <= n; i++){
		sum += ss[i];
		if (sum > r[i])
			return false;
    }
    return true;
}