记录编号	134513	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	JSX	是否通过	通过
代码语言	C++	运行时间	1.825 s
提交时间	2014-10-30 12:26:59	内存使用	15.57 MiB

#include <cstdio>
#include <climits>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=1001000;

int N=0,M=0,M1=0;
int T[MAXN<<2]={0};

inline void Insert(int s,int t,int v){
	int A=0;
	for(s=s+M1-1,t=t+M1+1;s^t^1;s>>=1,t>>=1){
		if (!(s&1)) T[s^1]+=v;
		if ( (t&1)) T[t^1]+=v;
		A=min(T[s],T[s^1]),T[s]-=A,T[s^1]-=A,T[s>>1]+=A;
		A=min(T[t],T[t^1]),T[t]-=A,T[t^1]-=A,T[t>>1]+=A;
	}
	for(;s>1;A=min(T[s],T[s^1]),T[s]-=A,T[s^1]-=A,T[s>>1]+=A,s>>=1);
}

inline int Query(int s,int t){
	int Lans=(1<<28),Rans=(1<<28);
	for(s=s+M1-1,t=t+M1+1;s^t^1;s>>=1,t>>=1){
		Lans+=T[s];	Rans+=T[t];
		if(!(s&1)) Lans=min(Lans,T[s^1]);
		if( (t&1)) Rans=min(Rans,T[t^1]);
	}
	int Res=min(Lans+T[s],Rans+T[t]);
	while(s>1) Res+=T[s>>=1];
	return Res;
}

int main(){
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(M1=1;M1<N+2;M1<<=1);
	for(int i=1;i<=N;++i) scanf("%d",&T[i+M1]);
	for(int i=M1;i>=1;i--){
		T[i]=min(T[i<<1],T[(i<<1)+1]);
		T[i<<1]-=T[i]; T[(i<<1)+1]-=T[i];
	}
	
	int jsx=true;
	int s=0,t=0,v=0;
	for(int i=1;i<=M;++i){
		scanf("%d%d%d",&v,&s,&t);
		Insert(s,t,-v);
		int temp=Query(s,t);
		if(temp<0){
			printf("-1\n%d",i); jsx=false; break;
		}
	}
	
	if(jsx)	printf("0\n");
	getchar(); getchar();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
*/