记录编号	131484	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	RP++	是否通过	通过
代码语言	C++	运行时间	3.684 s
提交时间	2014-10-24 15:46:13	内存使用	65.14 MiB

#include<cstdio>
#include<cctype>
using namespace std;
#define maxn 1000000
int nClass,nPlan;
int nData[maxn+10];
int add[maxn*4+10]={0};
int num,a,b;
int ans=0;
struct node{
	int l;
	int r;
	int mmin;
}f[maxn*4+10];
inline int zh_min(int m,int n)
{
	if(m>n)return n;
	return m;
}
inline void BuildTree(int root,int s,int t)
{
	f[root].l=s;
	f[root].r=t;
	if(s==t)f[root].mmin=nData[s];
	else
	{
		int mid=(s+t)>>1;
		BuildTree(root<<1,s,mid);
		BuildTree((root<<1)+1,mid+1,t);
		f[root].mmin=zh_min(f[root<<1].mmin,f[(root<<1)+1].mmin);
	}
}
inline void Update(int root)
{
	if(a<=f[root].l&&b>=f[root].r)
	{
		add[root]+=num;
		f[root].mmin-=num;
	}
	else
	{
		int mid=(f[root].l+f[root].r)>>1;
		if(mid>=a)Update(root<<1);
		if(mid<b)Update((root<<1)+1);
		f[root].mmin=zh_min(f[root<<1].mmin,f[(root<<1)+1].mmin)-add[root];
	}
}
inline void Query(int root,int other)
{
	if(a<=f[root].l&&b>=f[root].r)ans=zh_min(ans,f[root].mmin-other);
	else
	{
		int mid=(f[root].l+f[root].r)>>1;
		if(mid>=a)Query(root<<1,other+add[root]);
		if(mid<b)Query((root<<1)+1,other+add[root]);
	}
}
inline int getint()
{
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	int x=0;
	while(isdigit(ch))
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
int buf[10];
inline void writeint(int i)
{
	int p=0;
	if(i==0)p++;
	else while(i)
		 {
		 	buf[p++]=i%10;
		 	i/=10;
		 }
	for(int j=p-1;j>=0;j--)putchar('0'+buf[j]);
}
int main()
{
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	nClass=getint(),nPlan=getint();
	for(int i=1;i<=nClass;i++)nData[i]=getint();
	BuildTree(1,1,nClass);
	for(int i=1;i<=nPlan;i++)
	{
		num=getint(),a=getint(),b=getint();
		ans=0x7fffffff;
		Query(1,0);
		if(ans<num)
		{
			putchar('-');
			putchar(49);
			putchar('\n');
			writeint(i);
			putchar('\n');
			return 0;
		}
		Update(1);
	}
	putchar(48);
}