记录编号	187351	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	2.063 s
提交时间	2015-09-18 17:48:42	内存使用	23.20 MiB

#include <fstream>
#define N 1000010
using namespace std;
typedef long long ll;
ifstream in("classrooms.in");
ofstream out("classrooms.out");
int n,m;
int a[N]={0},d[N]={0},s[N]={0};
int L[N]={0},R[N]={0},D[N]={0};
bool check(int x)
{
	int i;
	ll sum=0;
	for(i=1;i<=n;i++)d[i]=a[i]-a[i-1];
	for(i=1;i<=x;i++)
	{
		d[L[i]]-=D[i];
		d[R[i]+1]+=D[i];
	}
	for(i=1;i<=n;i++)
	{
		sum+=d[i];
		if(sum<0)return 0;
	}
	return 1;
}
void read()
{
	int i;
	in>>n>>m;
	for(i=1;i<=n;i++)in>>a[i];
	for(i=1;i<=m;i++)in>>D[i]>>L[i]>>R[i];
}
void work()
{
	int i,l,r,mid;
	l=1;r=m;
	//out<<l<<' '<<r<<endl;
	while(l<r)
	{
		mid=(l+r)/2;
	    //out<<l<<' '<<r<<endl;
		if(!check(mid))r=mid;//(l,mid)
		else l=mid+1;//(mid+1,r)
	}
	if(r==m)out<<0<<endl;
	else
	{
		out<<-1<<endl;
		out<<l<<endl;
	}
}
int main()
{
	read();
	work();
	return 0;
}