记录编号	191670	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	1.743 s
提交时间	2015-10-08 15:06:51	内存使用	19.37 MiB

#include<cstdio>
#include<cstring>
using namespace std;
int b[1000005],a[1000005],A[1000006],B[1000006],C[1000006],n,m,l,r,ans,sum;
inline int in(){
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
	return x;
}
bool judge(int x){
	sum=0;
	memset(b,0,sizeof(b));
	for(int i=1;i<=x;++i) b[B[i]]+=A[i],b[C[i]+1]-=A[i];
	for(int i=1;i<=n;++i) {
		sum+=b[i]; if(sum>a[i]) return 0;
	}
	return 1;
}
int main(){
    freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	n=in(); m=in();
	for(int i=1;i<=n;++i) a[i]=in();
	for(int i=1;i<=m;++i){
		A[i]=in(); B[i]=in(); C[i]=in();
	}
	l=1;r=m;
	while(l<=r){
	  int mid=(l+r)>>1;
	  if(!judge(mid)){
			ans=mid; r=mid-1;
	  }
	  else l=mid+1;
	}
	if(!ans) puts("0");
	else {
		printf("-1\n%d",ans);
	}
}