http://wikioi.com/problem/1217/

wikioi_1217.cpp

#include <iostream>
#include <memory.h>
#include <cmath>
//#include <cstdio>
using namespace std;
int n,m;
long long tree[2000010];
long long treeeditor[2000010];
//获取l~r的下标 
int encode(int l,int r){
	return (l+r)|(l!=r);
}
//对lazy tag执行清空操作 
void clear(int l,int r,int val){
	tree[encode(l,r)]+=treeeditor[encode(l,r)];
	int mid=(l+r)/2;
	if(l!=r){
		treeeditor[encode(l,mid)]+=treeeditor[encode(l,r)]+val;
		treeeditor[encode(mid+1,r)]+=treeeditor[encode(l,r)]+val;
	}
	treeeditor[encode(l,r)]=0;
}
//l,r 需修改的段
//s,e 当前递归节点 
int modify(long long val,int l,int r,int s,int e){
	if(r<s||e<l){
		return 0;
	}
	int mid=(s+e)/2;
	if(l<=s&&r>=e){
		tree[encode(s,e)]+=val;
		clear(s,e,val);
		return 0;	
	}
	modify(val,l,r,s,mid);
	modify(val,l,r,mid+1,e);
	clear(s,mid,0);
	clear(mid+1,e,0);
	tree[encode(s,e)]=min(tree[encode(s,mid)],tree[encode(mid+1,e)]);
}
int main(){
	ios::sync_with_stdio(false);
	//scanf("%d %d",&n,&m);
	cin>>n>>m;
	memset(treeeditor,0,sizeof(treeeditor));
	for (int i=1;i<=n;i++){
		int num;
		//scanf("%d",&num);
		cin>>num;
		modify(num,i,i,1,n);
	}
	for (int i=1;i<=m;i++){
		int dj,sj,tj;
		//scanf("%d %d %d",&dj,&sj,&tj);
		cin>>dj>>sj>>tj;
		modify(-dj,sj,tj,1,n);
		if (tree[encode(1,n)]<0){
			cout<<"-1"<<endl<<i;
			return 0;
		}
	}
	cout<<"0";
	return 0;
}