记录编号	279116	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	2.866 s
提交时间	2016-07-08 20:02:35	内存使用	21.57 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lch l,mid,rt<<1
#define rch mid+1,r,rt<<1|1
using namespace std;
namespace mine{
	inline int getint(){
		static int __c,__x;
		static bool __neg;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline long long getll(){
		static long long __x;
		static char __c;
		static bool __neg;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline void putint(int __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
	inline void putll(long long __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
const int maxn=1000100;
void build(int,int,int);
void add(int,int,int,int,int,int);
int query(int,int,int,int,int);
void update(int);
int n,m,l,r,num;
int a[maxn<<2],lazy[maxn<<2]={0};
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
#endif
	n=getint();
	m=getint();
	build(1,n,1);
	for(int i=1;i<=m;i++){
		num=getint();
		l=getint();
		r=getint();
		add(l,r,-num,1,n,1);
		if(query(l,r,1,n,1)<0){
			putchar('-');
			putchar('1');
			putchar('\n');
			putint(i);
			return 0;
		}
	}
	putchar('0');
	return 0;
}
inline void build(int l,int r,int rt){
	if(l==r){
		a[rt]=getint();
		return;
	}
	int mid=(l+r)>>1;
	build(lch);
	build(rch);
	a[rt]=min(a[rt<<1],a[rt<<1|1]);
}
inline void add(int s,int t,int num,int l,int r,int rt){
	if(s<=l&&t>=r){
		a[rt]+=num;
		lazy[rt]+=num;
		return;
	}
	update(rt);
	int mid=(l+r)>>1;
	if(s<=mid)add(s,t,num,lch);
	if(t>mid)add(s,t,num,rch);
	a[rt]=min(a[rt<<1],a[rt<<1|1]);
}
inline int query(int s,int t,int l,int r,int rt){
	if(s<=l&&t>=r)return a[rt];
	update(rt);
	int mid=(l+r)>>1;
	if(t<=mid)return query(s,t,lch);
	if(s>mid)return query(s,t,rch);
	return min(query(s,t,lch),query(s,t,rch));
}
inline void update(int rt){
	int ch=rt<<1;
	a[ch]+=lazy[rt];
	lazy[ch]+=lazy[rt];
	ch|=1;
	a[ch]+=lazy[rt];
	lazy[ch]+=lazy[rt];
	lazy[rt]=0;
}
int main(){;}
int hzoier=MAIN();