记录编号	73112	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.697 s
提交时间	2013-10-20 10:12:19	内存使用	25.67 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const int SIZEN=1e6+100;
int r[SIZEN]={0},d[SIZEN]={0},s[SIZEN]={0},t[SIZEN]={0};
int n,m;
//本题中,差分数列第i项表示原数列i项-(i-1项)
void delta_to_ori(int dt[SIZEN],int a[SIZEN]){//将差分数列dt还原到原数列a,它们的长度均为n
	int i;
	for(i=1;i<=n;i++) a[i]=a[i-1]+dt[i];
}
void ori_to_delta(int a[SIZEN],int dt[SIZEN]){//原数列a产生差分数列dt,二者长度为n
	int i;
	for(i=1;i<=n;i++) dt[i]=a[i]-a[i-1];
}
bool legal(int a[SIZEN]){//判断对于每天剩余的教室数列a,是否供应足够(是则返回true)
	int i;
	for(i=1;i<=n;i++) if(a[i]<0) return false;
	return true;
}
void single_rent(int dt[SIZEN],int nows,int nowt,int nowd){//在差分数列dt中,对于nows到nowt每天租借nowd个教室
	dt[nows]-=nowd;
	dt[nowt+1]+=nowd;
}
void add_section_order(int nowdt[SIZEN],int dt[SIZEN],int x,int y){
	//将第x~y天的订单加在差分数列nowdt上,结果传回dt
	int i;
	for(i=1;i<=n;i++) dt[i]=nowdt[i];
	for(i=x;i<=y;i++) single_rent(dt,s[i],t[i],d[i]);
}
void assign(int a[SIZEN],int b[SIZEN]){//a赋值为b,二者长度为n
	int i;
	for(i=1;i<=n;i++) a[i]=b[i];
}
int delta[SIZEN]={0},ldelta[SIZEN]={0};//ldelta表示累计到当前二分区间左边界-1上的差分数列
int left_room[SIZEN]={0};
int find(int x,int y){//在[x,y]内查找
	if(x==y) return x;
	int mid=(x+y)>>1;
	add_section_order(ldelta,delta,x,mid);
	delta_to_ori(delta,left_room);
	if(legal(left_room)){//[x,mid]区间不会冲突,检测后半区间
		assign(ldelta,delta);
		return find(mid+1,y);
	}
	else return find(x,mid);
}
void read(void){
	scanf("%d%d",&n,&m);
	int i;
	for(i=1;i<=n;i++) scanf("%d",&r[i]);
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&d[i],&s[i],&t[i]);
	}
}
void work(void){
	ori_to_delta(r,ldelta);
	int ans=find(1,n+1);
	if(ans==n+1) printf("0\n");
	else printf("-1\n%d\n",ans);
}
int main(){
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	read();
	work();
	return 0;
}