记录编号	458515	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	芒硝	是否通过	通过
代码语言	C++	运行时间	3.212 s
提交时间	2017-10-11 15:24:09	内存使用	34.65 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=1000000+10;
int t[maxn*4],lazy[maxn*4],s[maxn];
int n,m,x,y,z,g;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void build(int o,int l,int r)
{
	if(l==r){t[o]=s[l];return;}
	else{
	int ls=o<<1,rs=o<<1|1,mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	t[o]=min(t[ls],t[rs]);
	}
}
void push(int o)
{
	int ls=o<<1,rs=o<<1|1;
	t[ls]+=lazy[o];
	lazy[ls]+=lazy[o];
	t[rs]+=lazy[o];
	lazy[rs]+=lazy[o];
	lazy[o]=0;
}//Sad
void add(int o,int l,int r)
{
	if(l>=x&&y>=r){
	t[o]+=z;
	lazy[o]+=z;
	return;
	}
	push(o);
	int ls=o<<1,rs=o<<1|1,mid=(l+r)>>1;
	if(mid>=x)add(ls,l,mid);
	if(y>mid)add(rs,mid+1,r);
	t[o]=min(t[ls],t[rs]);
	return;
}
int query(int o,int l,int r)
{
	int ls=o<<1,rs=o<<1|1,mid=(l+r)>>1,ans=1000000010;
	if((l>=x)&&(r<=y)){return t[o];}
	push(o);
	if(mid>=x)ans=min(ans,query(ls,l,mid));
	if(y>mid)ans=min(ans,query(rs,mid+1,r));
//	cout<<l<<" "<<r<<" "<<ans<<endl;
    return ans;
}
int main()
{
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
	s[i]=read();
	build(1,1,n);
	int flag=1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&z,&x,&y);
		z=-z;
	//	cout<<query(1,1,n)<<endl ;
		if(query(1,1,n)+z<0)
		{
			puts("-1");
			printf("%d",i);
			return 0;
		}
	    else{
		add(1,1,n);
		
		}
	}
	puts("0");
	return 0;
}