记录编号	328937	评测结果	AAAAAAAAAAAAAAAAATAT
题目名称	[NOIP 2012]借教室	最终得分	90
用户昵称	Marvolo	是否通过	未通过
代码语言	C++	运行时间	5.105 s
提交时间	2016-10-24 18:48:05	内存使用	34.29 MiB

#include<cstdio>
#include<cstring>
using namespace std;
 
int i,n,m,s,x,y;
int a[500010];
 
struct Marvolo{int d,l,r,p,mid;}t[2000010];
 
inline int min(int a,int b){return (a<b)?a:b;}
inline int read(){
	int p=0; char c=getchar();
	while (c<'0'||c>'9')  c=getchar();
	while (c>='0'&&c<='9')	p=p*10+c-48,c=getchar();
	return p;
}
	inline void Maketree(int x,int l,int r){
		int Mid=(l+r)>>1;
		t[x].l=l;	t[x].r=r;	t[x].mid=Mid;
		if (l==r)	{t[x].d=a[l]; return;}
		Maketree(x<<1,l,Mid);	Maketree((x<<1)+1,Mid+1,r);
		t[x].d=min(t[x<<1].d,t[(x<<1)+1].d);
	}
	inline void Clear(int X){
		t[X<<1].d-=t[X].p;	t[(X<<1)+1].d-=t[X].p;
		t[X<<1].p+=t[X].p;	t[(X<<1)+1].p+=t[X].p;
		t[X].p=0;
	}
	inline void Insert(int x,int low,int high){
		if (t[x].l==low&&t[x].r==high){
			t[x].d-=s;	t[x].p+=s;	return;}
		if (t[x].p)	Clear(x);
		if (high<=t[x].mid)	Insert(x<<1,low,high);	else
		if (low>t[x].mid)	Insert((x<<1)+1,low,high);	else{
			Insert(x<<1,low,t[x].mid);	Insert((x<<1)+1,t[x].mid+1,high);
		}
		t[x].d=min(t[x<<1].d,t[(x<<1)+1].d);
	}
inline void Work(){
	int i=0;
	Maketree(1,1,n);
	for (i=1;i<=m;i++){
		s=read();	x=read();	y=read();
		Insert(1,x,y);
		if (t[1].d<0)	{printf("-1\n"); printf("%d\n",i);	return;}
	}
	printf("0\n");
}
 
int main(){
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	n=read();	m=read();
	for (i=1;i<=n;i++)	a[i]=read();
	Work();
	return 0;
}