记录编号	181430	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	4.371 s
提交时间	2015-08-25 11:05:30	内存使用	17.45 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int tem[1000010];
int n,m,r[1000010]={0},d[1000010]={0},s[1000010]={0},t[1000010]={0};
bool pan(int k)
{
	memset(tem,0,sizeof(tem));
	for(int i=1;i<=n;i++)
		tem[i]=r[i]-r[i-1];
	for(int i=1;i<=k;i++)
	{
		tem[s[i]]-=d[i];
		tem[t[i]+1]+=d[i];
	}
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=tem[i];
		//cout<<tem[i]<<endl;
		if(sum<0) return 0;
	}
	return 1;
}
int main()
{
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&r[i]);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&d[i],&s[i],&t[i]);
	int L=1,R=m;
	while(L<R)
	{
		int mid=(L+R)/2;
		//cout<<L<<" "<<R<<endl;
		if(pan(mid)) L=mid+1;
		else R=mid;
	}
	if(R==m) printf("0\n");
	else printf("-1\n%d\n",L);
	return 0;
}