记录编号	467756	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	小字、小瓶子	是否通过	通过
代码语言	C++	运行时间	1.604 s
提交时间	2017-10-31 09:11:53	内存使用	19.39 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
const int maxn=1000005;
using namespace std;
struct nn{
	int d;
	int s;
	int t;
}np[maxn];
int n,m,cla[maxn],q[maxn];
int check(int x)
{
	int sum=0;
	memset(q,0,sizeof(q));
	for(int i=1;i<=x;i++) {
		q[np[i].s]+=np[i].d;
		q[np[i].t+1]-=np[i].d;
	}
	for(int i=1;i<n;i++) {
		sum+=q[i];
		if(sum>cla[i]) return 0;
	}
	return 1;
}
int main()
{
	
    freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&cla[i]);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&np[i].d,&np[i].s,&np[i].t);
	int l=1,r=m;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	if(l>m) printf("0");
	else printf("-1\n%d",l);
	return 0;
}