记录编号	448294	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1266.[NOIP 2012]借教室	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	1.554 s
提交时间	2017-09-12 15:40:08	内存使用	12.81 MiB

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000001;
int n,m,r[maxn],d[maxn],s[maxn],t[maxn],L,R,ans,i;
bool check(int now)
{
	int x[maxn],sum=0;
	memset(x,0,sizeof(x));
	for(int j=1;j<=now;j++)
	{
		x[s[j]]+=d[j];
		x[t[j]+1]-=d[j];
	}
	for(int j=1;j<=n;j++)
	{
		sum+=x[j];
		if(sum>r[j])return 0;
	}
	return 1;
}
int Main()
{
	freopen("classrooms.in","r",stdin);freopen("classrooms.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&r[i]);
	for(i=1;i<=m;i++)scanf("%d%d%d",&d[i],&s[i],&t[i]);
	L=1;R=m;
	while(L<=R)
	{
		int mid=L+((R-L)>>1);
		if(check(mid))L=mid+1;
		else{ans=mid;R=mid-1;}
	}
	if(ans)printf("-1\n");
	printf("%d\n",ans);
	return 0;
}
int main(){;}
int syy=Main();