记录编号	121033	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	1.773 s
提交时间	2014-09-17 19:55:34	内存使用	19.39 MiB

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cctype>
#include <algorithm>
using namespace std;
#define maxn ((int)1e6 + 5)
FILE *in = fopen("classrooms.in","r");
FILE *out = fopen("classrooms.out","w");
int n,m,r[maxn],d[maxn],s[maxn],t[maxn],dif[maxn];
int getint(){
	int ans=0;char c;
	c = fgetc(in);
	while(!isdigit(c))c = fgetc(in);
	while(isdigit(c)){
		ans = ans*10 + c - '0';
		c = fgetc(in);
	}
	return ans;
}
bool judge(int k){
	int i,sum=0;
	dif[0]=r[1];
	for(i=1;i<n;++i)dif[i] = r[i+1] - r[i];//"可使用数量"差分数列
	for(i=1;i<=k;++i){
		dif[s[i]-1] -= d[i];
		dif[t[i]] += d[i];
	}
	for(i=1;i<=n;++i){
		sum += dif[i-1];
		if(sum  < 0)return 0;
	}
	return 1;
}
int main(){
	n = getint();m = getint();
	int i,L=1,R=m,k;
	for(i=1;i<=n;++i)r[i] = getint();
	for(i=1;i<=m;++i)d[i]=getint(),s[i]=getint(),t[i]=getint();
	while(L<=R){
		k = (L+R) >> 1;
		if(judge(k))L = k + 1;
		else R = k - 1;
	}
	if(R == m)fprintf(out,"0\n");
	else fprintf(out,"-1\n%d\n",L);
	return 0;
}