记录编号	200516	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	thomount	是否通过	通过
代码语言	C++	运行时间	1.796 s
提交时间	2015-10-28 21:30:58	内存使用	32.89 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int read() {
	char ch = getchar();
	while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
	int ans = 0, flag = 1;
	if (ch == '-') flag = -1, ch = getchar();
	while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
	return ans * flag;
}
const int N = 1000010;
struct point {
	int x, w, s;
	point(int s = 0, int w = 0, int x = 0): x(x), w(w), s(s) {}
} p[2*N];
bool operator < (point a, point b) {
	return (a.w < b.w);
}
int d[N], f[N], a[N];
int main() {
	freopen("classrooms.in", "r", stdin);
	freopen("classrooms.out", "w", stdout);
	int n = read(), m = read();
	
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 1; i <= m; i++) {
		int D = read(), L = read(), R = read();
		d[i] = D;
		p[2*i-1] = point(D, L, i);
		p[2*i] = point(-D, R+1, i);
	}
	
	sort(p+1, p+2*m+1);
	int st = 1, bad = m+1;
	memset(f, 0, sizeof(f));
	long long S = 0;
	for (int i = 1; i <= n; i++) {
		while (st <= 2*m && p[st].w == i) {
			if (p[st].x <= bad) {
				S += p[st].s;
				if (p[st].s < 0) f[p[st].x] = 0; else f[p[st].x] = 1;
			}
			st++;
		}
		if (S > a[i]) {
			while (bad > 1 && S > a[i]) {
				if (f[bad-1]) {
					S -= d[bad-1];
					f[bad-1] = 0;
				}
				bad--;
			}
		}
		if (bad == 1) break;
	}
	
	if (bad == m+1) printf("0\n"); else printf("-1\n%d\n", bad);
	return 0;
}