记录编号	427726	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	1.078 s
提交时间	2017-07-22 23:43:17	内存使用	17.43 MiB

#include<cstdio>
#include<cctype>
const int maxn=1e6+5;
using namespace std;
inline int get();
int n,m;
int r[maxn],d[maxn],s[maxn],t[maxn],now[maxn];
int main()
{
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	n=get();m=get();
	for(int i=1;i<=n;i++)r[i]=get();
	for(int i=1;i<=m;i++)d[i]=get(),s[i]=get(),t[i]=get();
	int l=1,rr=m;
	for(;l<rr;)
	{
		int mid=(l+rr)>>1;
		for(int ll=l;ll<=mid;ll++)now[s[ll]]+=d[ll],now[t[ll]+1]-=d[ll];
		long long sum=0;bool jud=0;
		for(int i=1;i<=n;i++)
		{
			sum+=now[i];
			if(sum>r[i])
			{
				jud=1;
				break;
			}
		}
		if(!jud)l=mid+1;
		else
		{
			rr=mid;
			for(int ll=l;ll<=mid;ll++)now[s[ll]]-=d[ll],now[t[ll]+1]+=d[ll];
		}
	}
	if(l==m)printf("0");
	else printf("-1\n%d",l);
	return 0;
}
inline int get()
{
	int t=0,j=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')j=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return j*t;
}