[NOIp2012提高组]借教室

OJ题号：洛谷1083

思路：ZKW线段树

 #include<cstdio>

 #include<cctype>

 #include<algorithm>

 inline int getint() {

     char ch;

     while(!isdigit(ch=getchar()));

     int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=;

 class ZKW {

     #define _left <<1

     #define _right <<1|1

     private:

         int m,val[N<<],tag[N<<];

     public:

         void build(const int n) {

             for(m=;m<=n;m<<=);

             for(int i=;i<=n;i++) val[m+i]=getint();

             for(int i=m;i;i--) val[i]=std::min(val[i _left],val[i _right]);

         }

         void modify(int l,int r,int x) {

             for(l+=m-,r+=m+;l^r^;l>>=,r>>=) {

                 if(l<m) val[l]=std::min(val[l _left],val[l _right])-tag[l];

                 if(~l&) val[l^]-=x,tag[l^]+=x;

                 if(r<m) val[r]=std::min(val[r _left],val[r _right])-tag[r];

                 if(r&) val[r^]-=x,tag[r^]+=x;

             }

             for(;l&&r;l>>=,r>>=) {

                 val[l]=std::min(val[l _left],val[l _right])-tag[l];

                 val[r]=std::min(val[r _left],val[r _right])-tag[r];

             }

         }

         bool check() {

             return val[]>=;

         }

 };

 ZKW tree;

 int main() {

     int n=getint(),m=getint();

     tree.build(n);

     for(int i=;i<=m;i++) {

         int d=getint(),s=getint(),t=getint();

         tree.modify(s,t,d);

         if(!tree.check()) {

             printf("-1\n%d\n",i);

             return ;

         }

     }

     puts("");

     return ;

 }