记录编号	332351	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	3.483 s
提交时间	2016-10-28 18:50:17	内存使用	19.37 MiB

#include<cstdio>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("classrooms.in","r",stdin);freopen("classrooms.out","w",stdout);chul();Cu
const int maxn=1000010;
int a[maxn],b[maxn];
int n,m,lstx;
struct op{
	int n,s,t;
}r[maxn];
bool JUDGE(int x){
	if(lstx>x){
		for(int i=x+1;i<=lstx;i++){
			b[r[i].s]+=r[i].n;
			b[r[i].t+1]-=r[i].n;
		}
	}
	else{
		for(int i=lstx+1;i<=x;i++){
			b[r[i].s]-=r[i].n;
			b[r[i].t+1]+=r[i].n;
		}
	}
	int cnt=0;
	bool f=1;
	for(int i=1;i<=n;i++){
		cnt+=b[i];
		if(cnt<0){
			f=0;
			break;
		}
	}
	return f;
}
void chul(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i]-a[i-1];
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&r[i].n,&r[i].s,&r[i].t);
		b[r[i].s]-=r[i].n;
		b[r[i].t+1]+=r[i].n;
	}
	lstx=m;
	int cnt=0;
	bool f=1;
	for(int i=1;i<=n;i++){
		cnt+=b[i];
		if(cnt<0){
			f=0;
			break;
		}
	}
	if(f){
		printf("0\n");
		return;
	}
	printf("-1\n");
	int l=1,r=m,mid,ans=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(JUDGE(mid)){
			ans=mid;
			l=mid+1;
		}
		else r=mid-1;
		lstx=mid;
	}
	printf("%d\n",ans+1);
}
int main(){
	Begin;
	chul();while(1);
}