记录编号	67906	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	Hobo	是否通过	通过
代码语言	C++	运行时间	2.531 s
提交时间	2013-08-15 13:49:00	内存使用	16.48 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define ULL unsigned long long
#define MAXN 1000000+10
using namespace std;
int N,M,L,R,NOW,K,SSUM,ROOM[MAXN],D[MAXN],S[MAXN],T[MAXN],SUM[MAXN];
bool F;

void init()
{
cin>>N>>M;
for (int i=1;i<=N;i++) scanf("%d",&ROOM[i]);
for (int i=1;i<=M;i++) scanf("%d%d%d",&D[i],&S[i],&T[i]);
}

void print()
{
cout<<"0"<<endl;
exit(0);
}

void work()
{
NOW=0;
L=0;
R=M+1;
do {
	F=1;
	K=(L+R)>>1;
	if (K>NOW) 
		for (int i=NOW+1;i<=K;i++)
		{
		SUM[S[i]]+=D[i];
		SUM[T[i]+1]-=D[i];
		}
	else
		for (int i=K+1;i<=NOW;i++)
		{
		SUM[S[i]]-=D[i];
		SUM[T[i]+1]+=D[i];
		}
	NOW=K;
	SSUM=0;
	for (int i=1;i<=N;i++)
		{
		SSUM+=SUM[i];
		if (SSUM>ROOM[i]) {F=0;break;}
		}
	if (F) L=K+1; else R=K;
	}
while (L!=R);
if (K==M && F) print();
cout<<"-1"<<endl;
cout<<L;
}

int main()
{
freopen("classrooms.in","r",stdin);
freopen("classrooms.out","w",stdout);
init();
work();
return 0;
}