记录编号	191675	评测结果	TTTTTTTATTTTTTTTTTTT
题目名称	[NOIP 2012]借教室	最终得分	5
用户昵称	lenibomb	是否通过	未通过
代码语言	C++	运行时间	19.036 s
提交时间	2015-10-08 15:10:28	内存使用	27.29 MiB

#define MAXN 1000010UL

#include<cstdio>
using namespace std;

int n,m,op[MAXN][3],d[MAXN];
//op:0 个数 1 起始时间 2 结束时间
int ls,rs,ans;

int sum[MAXN],seq[MAXN];

bool check(int mid){
	for(int i=1;i<=mid;i++){
		seq[op[i][1]]+=op[i][0];
		seq[op[i][2]+1]-=op[i][0];
	}
	for(int i=1;i<=n;i++){
		seq[i]+=seq[i-1];seq[i-1]=0;
		if(seq[i]>d[i]) {
			for(int j=i;j<=n;j++) seq[j]=0;
			return false;
		}
	}
	seq[n]=0;
	if(ans<mid) ans=mid;
	return true;
}

int main(){
    freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&d[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&op[i][0],&op[i][1],&op[i][2]);
	}
	ls=1,rs=m;
	while(ls<=rs){
		int mid=(ls+rs)/2;
		if(check(mid)) ls=mid+1;
		else rs=mid+1;
	}
	if(ans==m) printf("0");
	else printf("-1\n%d",ans+1);
	getchar(); getchar(); getchar();
}