洛谷P1083题解

#include<bits/stdc++.h>
#define ____ ((__+___)>>1)
#define length(__,___)  (___-__+1)
#define FOR(i,l,r) for (int i=l;i<=r;i++)
using namespace std;
const int N  = 1000100;
bool flag=0;
int d,s,t,r[N],n,m;
struct Node {
int num,lz,mi;
}
nd[N*4];
inline int read() {register int f=1,k=0;register char c=getchar();while(c!='-'&&(c<'0'||c>'9')) {
c=getchar();
}
if(c=='-') {
f=-1,c=getchar();
}
while(c>='0'&&c<='9') {
k=(k<<3)+(k<<1)+(c^48),c=getchar();
}
return f*k;
}
void pushup(int _) {
nd[_].num=nd[_*2].num+nd[_*2+1].num;
nd[_].mi = min(nd[_*2].mi,nd[_*2+1].mi);
}
void build(int _,int __,int ___) {
if(__ == ___) {
nd[_].num=nd[_].mi=r[__];
return;
} else {
build(_*2,__,____);
build(_*2+1,____+1,___);
pushup(_);
}
}
void pushdown(int _,int __,int ___) {
if(nd[_].lz) {
nd[_*2].lz+=nd[_].lz;
nd[_*2+1].lz+=nd[_].lz;
nd[_*2].num+=nd[_].lz*length(__,____);
nd[_*2+1].num+=nd[_].lz*length(____+1,___);
nd[_*2].mi+=nd[_].lz;
nd[_*2+1].mi+=nd[_].lz;
nd[_].lz=0;
}
}
void update(int _,int __,int ___,int x,int y,int k) {
if(x<=__&&___<=y) {
nd[_].lz-=k;
nd[_].num-=k*length(__,___);
nd[_].mi-=k;
if(nd[_].mi<0) {
flag=1;
}
return;
}
pushdown(_,__,___);
if(x<=____) update(_*2,__,____,x,y,k);
    if(y>____) update(_*2+1,____+1,___,x,y,k);
pushup(_);
}
void DBG(int _,int __,int ___){
if(__==___){
return;
}
cout<<_<<" "<<__<<" "<<___<<" "<<nd[_].lz<<" "<<nd[_].mi<<" "<<nd[_].num<<endl;
DBG(_*2,__,____);
DBG(_*2+1,____+1,___);
 
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
cin>>n>>m;
FOR(i,1,n) {
r[i]=read();
}
build(1,1,n);//printf("i l r lz mi num\n");
// DBG(1,1,n);
// printf("\n");
FOR(i,1,m) {
if(flag==1) {
printf("-1\n%d\n",i-1);
return 0;
}
cin>>d>>s>>t;
update(1,1,n,s,t,d);
// DBG(1,1,n);
// printf("\n");
 
}
printf("0\n");
return 0;
}