记录编号	313132	评测结果	AAAAAAAWAAAAAAATATTT
题目名称	[NOIP 2012]借教室	最终得分	75
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	7.469 s
提交时间	2016-09-28 16:23:40	内存使用	23.18 MiB

#include<cstdio>
#include<climits>
using namespace std;
const int N=1000010;
int l[N],r[N],s[N],k[N],Min[N],add[N],root,n,m;
inline int min(int x,int y){return x<y?x:y;}
inline void update(int x){
	s[x]=s[l[x]]+s[r[x]]+1;
	Min[x]=min(k[x],min(Min[l[x]],Min[r[x]]));
}
inline void pushdown(int x){
	if (add[x]){
		if (l[x]) k[l[x]]+=add[x],add[l[x]]+=add[x],Min[l[x]]+=add[x];
		if (r[x]) k[r[x]]+=add[x],add[r[x]]+=add[x],Min[r[x]]+=add[x];
		add[x]=0;
	}
}
inline void l_rotate(int &x){
	int y=r[x];
	r[x]=l[y];l[y]=x;
	update(x);update(y);
	x=y;
}
inline void r_rotate(int &x){
	int y=l[x];
	l[x]=r[y];r[y]=x;
	update(x);update(y);
	x=y;
}
void splay(int &x,int k){
	pushdown(x);
	int i=s[l[x]]+1;
	if (i==k) return;
	if (k<i) splay(l[x],k),r_rotate(x);
		else splay(r[x],k-i),l_rotate(x);
}
int build(int L,int R){
	if (L>R) return 0;
	int mid=(L+R)>>1;
	s[mid]=R-L+1;
	l[mid]=build(L,mid-1);
	r[mid]=build(mid+1,R);
	update(mid);
	return mid;
}
inline int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x;
}
int main()
{
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	n=read();m=read();
	for (int i=2;i<=n+1;i++) k[i]=read();
	Min[0]=k[0]=INT_MAX;
	root=build(1,n+2);
	for (int i=1;i<=m;i++){
		int c=read(),L=read(),R=read();
		splay(root,L);
		splay(root,R+2);
		int x=r[l[root]];
		if (Min[x]<c){printf("-1\n%d\n",i);return 0;}
		add[x]-=c;Min[x]-=c;k[x]-=c;
	}
	return 0;
}