记录编号	468274	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	1.327 s
提交时间	2017-10-31 20:27:07	内存使用	19.39 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 1000000000
#define N 1000005
using namespace std;
int read()
{
	int sum=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9'){sum=(sum<<3)+(sum<<1)+x-'0';x=getchar();}
	return sum*f;
}
int n,m,a[N],l1[N],r1[N],d[N],tot,s[N];
inline bool check(int x)
{
	memset(s,0,sizeof(s));
	for(int i=1;i<=x;i++)
		s[l1[i]]+=d[i],s[r1[i]+1]-=d[i];
	for(int i=1;i<=n;i++)
	{
		s[i]+=s[i-1];
		if(s[i]>a[i])return 0;
	}
	return 1;
}
int main()
{
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1,l,r,x;i<=m;i++)
		d[i]=read(),l1[i]=read(),r1[i]=read();
	int l=1,r=n,mid;
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	if(l-1==n)printf("0\n");
	else printf("-1\n%d",r+1);
}