记录编号	74354	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	QWERTIer	是否通过	通过
代码语言	C++	运行时间	3.428 s
提交时间	2013-10-24 22:09:10	内存使用	19.37 MiB

#include <stdio.h>
#define maxn 1000010
#define For(i,b,e) for(int i=b; i<=e; i++)
int l[maxn],r[maxn],cap[maxn],dec[maxn],cnt[maxn]={0};
int main(){
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	For(i,1,n)
		scanf("%d",&cap[i]);
	For(i,1,m){
		scanf("%d%d%d",&dec[i],&l[i],&r[i]);
		cnt[l[i]]+=dec[i];
		cnt[r[i]+1]-=dec[i];
	}
	int cur=m,a=0;
	For(i,1,n){
		a+=cnt[i];
		//printf(" %d %d %d\n",i,a,cap[i]);
		while(cur>=1&&a>cap[i]){
			if(i>=l[cur]&&i<=r[cur])a-=dec[cur];
			cnt[l[cur]]-=dec[cur];
			cnt[r[cur]+1]+=dec[cur];
			cur--;
		}
		//printf(" %d %d %d %d\n",i,a,cap[i],cur);
	}
	if(cur==m)
		printf("0\n");
	else
		printf("-1\n%d\n",cur+1);
	return 0;
}