Submission #940977

#	Time	Username	Problem	Language	Result	Execution time	Memory
940977		Warinchai	Progression (NOI20_progression)	C++14	0 / 100	3059 ms	55012 KiB

Progression

#include<bits/stdc++.h>
using namespace std;
int inf=1e9;
struct segtree{
    struct node{
        int pre,suf,vpre,vsuf,mx,sz;
        node(int x=0){
            pre=suf=0;
            mx=1;
            vpre=vsuf=x;
        }
        friend node operator+(node a,node b){
            node c;
            c.vpre=a.vpre;
            if(a.pre==a.sz&&a.vpre==b.vpre)c.pre=a.pre+b.pre;
            else c.pre=a.pre;
            c.vsuf=b.vsuf;
            if(b.suf==b.sz&&b.vsuf==a.vsuf)c.suf=a.suf+b.suf;
            else c.suf=b.suf;
            c.mx=max({a.mx,b.mx,(a.vsuf==b.vpre?a.suf+b.pre:0)});
            c.sz=a.sz+b.sz;
            return c;
        }
    };
    node info[1200005];
    int lset[1200005];
    int lmath[1200005];
    void push(int st,int en,int i){
        if(lset[i]!=0){
            info[i].pre=info[i].suf=info[i].mx=info[i].sz;
            info[i].vpre=info[i].vsuf=0;
            if(st!=en)lset[i*2]=lset[i*2+1]=lset[i],lmath[i*2]=lmath[i*2+1]=0;
            lset[i]=0;
        }
        if(lmath[i]!=0){
            info[i].vpre+=lmath[i];
            info[i].vsuf+=lmath[i];
            if(st!=en)lmath[i*2]+=lmath[i],lmath[i*2+1]+=lmath[i];
            lmath[i]=0;
        }
    }
    void upd(int st,int en,int i,int pos,int val){
        if(st>pos||en<pos)return;
        //cerr<<st<<" "<<en<<" "<<i<<"\n";
        push(st,en,i);
        if(st==en){
            //cerr<<"yes:"<<val<<"\n";
            info[i].vpre+=val;
            info[i].vsuf+=val;
            //cerr<<info[i].vpre<<"\n";
            return;
        }
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        info[i]=info[i*2]+info[i*2+1];
    }
    void upd_set(int st,int en,int i,int l,int r){
        if(st>r||en<l)return;
        push(st,en,i);
        if(st>=l&&en<=r){
            lset[i]=1;
            push(st,en,i);
            return;
        }
        int m=(st+en)/2;
        upd_set(st,m,i*2,l,r);
        upd_set(m+1,en,i*2+1,l,r);
        info[i]=info[i*2]+info[i*2+1];
    }
    void upd_math(int st,int en,int i,int l,int r,int val){
        if(st>r||en<l)return;
        push(st,en,i);
        if(st>=l&&en<=r){
            lmath[i]+=val;
            push(st,en,i);
            return;
        }
        int m=(st+en)/2;
        upd_math(st,m,i*2,l,r,val);
        upd_math(m+1,en,i*2+1,l,r,val);
    }
    node fval(int st,int en,int i,int l,int r){
        push(st,en,i);
        if(st==en)return info[i];
        int m=(st+en)/2;
        if(l<=m&&r>m)return fval(st,m,i*2,l,r)+fval(m+1,en,i*2+1,l,r);
        else if(l>m)return fval(m+1,en,i*2+1,l,r);
        else return fval(st,m,i*2,l,r);
    }
    void build(int st,int en,int i){
        if(st==en){
            info[i].pre=info[i].suf=info[i].mx=info[i].sz=1;
            info[i].vpre=info[i].vsuf=0;
            return;
        }
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=info[i*2]+info[i*2+1];
    }
}tr;
struct segvaltree{
    int info[1200005];
    int math[1200005];
    int add[1200005];
    int set[1200005];
    void push(int st,int en,int i){
        if(set[i]!=0){
            if(st==en)info[i]=0;
            else {
                set[i*2]=set[i*2+1]=set[i];
                math[i*2]=math[i*2+1]=add[i*2]=add[i*2+1]=0;
            }
            set[i]=0;
        }
        if(math[i]!=0){
            if(st!=en){
                math[i*2]+=math[i];
                math[i*2+1]+=math[i];
                add[i*2+1]+=((st+en)/2-st+1)*math[i];
            }
            math[i]=0;
        }
        if(add[i]!=0){
            if(st==en)info[i]+=add[i];
            else{
                add[i*2]+=add[i];
                add[i*2+1]+=add[i];
            }
            add[i]=0;
        }
    }
    void upd_set(int st,int en,int i,int l,int r){
        if(st>r||en<l)return;
        push(st,en,i);
        if(st>=l&&en<=r){
            set[i]=1;
            push(st,en,i);
            return;
        }
        int m=(st+en)/2;
        upd_set(st,m,i*2,l,r);
        upd_set(m+1,en,i*2+1,l,r);
    }
    void upd_add(int st,int en,int i,int l,int r,int val){
        //cerr<<st<<" "<<en<<" "<<i<<" "<<l<<" "<<r<<"\n";
        if(st>r||en<l)return;
        push(st,en,i);
        if(st>=l&&en<=r){
            //cerr<<"yes"<<"\n";
            add[i]=val;
            push(st,en,i);
            return;
        }
        int m=(st+en)/2;
        upd_add(st,m,i*2,l,r,val);
        upd_add(m+1,en,i*2+1,l,r,val);
    }
    void upd_math(int st,int en,int i,int l,int r,int val,int begin){
        if(st>r||en<l)return;
        push(st,en,i);
        if(st>=l&&en<=r){
            math[i]=val;
            int dif=st-begin;
            add[i]=dif*val;
            push(st,en,i);
            return;
        }
        int m=(st+en)/2;
        upd_math(st,m,i*2,l,r,val,begin);
        upd_math(m+1,en,i*2+1,l,r,val,begin);
    }
    int find(int st,int en,int i,int pos){
        push(st,en,i);
        int m=(st+en)/2;
        if(st==en)return info[i];
        if(pos<=m)return find(st,m,i*2,pos);
        else return find(m+1,en,i*2+1,pos);
    }
}val;
int ar[300005];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
        val.upd_add(1,n,1,i,i,ar[i]);
        //for(int i=1;i<=n;i++)cerr<<val.find(1,n,1,i)<<" ";
        //cerr<<"\n";
    }
    tr.build(1,n-1,1);
    /*cerr<<"INFO BF UPD:\n";
    for(int i=1;i<n;i++){
        cerr<<tr.fval(1,n-1,1,i,i).vpre<<" "<<tr.fval(1,n-1,1,i,i).mx<<"\n";
    }
    cerr<<"\n";
    cerr<<"UPDATING:\n";*/
    for(int i=1;i<n;i++){
        //cerr<<"I:"<<i<<"\n";
        tr.upd(1,n-1,1,i,ar[i+1]-ar[i]);
        //cerr<<"\n";
        //cerr<<i<<" "<<ar[i+1]-ar[i]<<" "<<tr.fval(1,n-1,1,i,i).vpre<<"\n";
    }
    //tr.upd(1,n,1,n,-inf);
    /*cerr<<"DIF:\n";
    for(int i=1;i<=n;i++){
        cerr<<tr.fval(1,n-1,1,i,i).vpre<<" ";
    }*/
    //cerr<<"\n";
    //for(int i=1;i<=n;i++)cerr<<val.find(1,n,1,i)<<" ";
    //cerr<<"\n\n\n";
    for(int i=0;i<q;i++){
        int x;cin>>x;
        if(x==1){
            int l,r,s,c;cin>>l>>r>>s>>c;
            //cerr<<"I:"<<i<<" "<<l<<" "<<r<<" "<<s<<" "<<c<<"\n";
            int bf=val.find(1,n,1,l-1);
            int curl=val.find(1,n,1,l);
            int af=val.find(1,n,1,r+1);
            int curr=val.find(1,n,1,r);
            int curdifl=tr.fval(1,n-1,1,l,l).vpre;
            int curdifr=tr.fval(1,n-1,1,r,r).vpre;
            //cerr<<bf<<" "<<curl<<" "<<af<<" "<<curr<<"\n";
            tr.upd(1,n-1,1,l-1,curl+s-bf-curdifl);
            //cerr<<"tree upd:"<<af-curr-s-c*(r-l)-curdifr<<"\n";
            tr.upd(1,n-1,1,r,af-curr-s-c*(r-l)-curdifr);
            //for(int i=1;i<=n;i++)cerr<<tr.fval(1,n-1,1,i,i).vpre<<" ";
            //cerr<<"\n";
            tr.upd_math(1,n-1,1,l,r-1,c);
            val.upd_add(1,n,1,l,r,s);
            //cerr<<"val:"<<curr+s+c*(r-l)<<"\n";
            //cerr<<"after add: ";
            //for(int i=1;i<=n;i++)cerr<<val.find(1,n,1,i)<<" ";
            //cerr<<"\n";
            val.upd_math(1,n,1,l,r,c,l);
            //cerr<<"after math: ";
            //for(int i=1;i<=n;i++)cerr<<val.find(1,n,1,i)<<" ";
            //cerr<<"\n";
        }else if(x==2){
            //cerr<<"REWRITE\n";
            int l,r,s,c;cin>>l>>r>>s>>c;
            int bf=val.find(1,n,1,l-1);
            int af=val.find(1,n,1,r+1);
            int curdifl=tr.fval(1,n-1,1,l,l).vpre;
            int curdifr=tr.fval(1,n-1,1,r,r).vpre;
            //cerr<<"bf,af:"<<bf<<" "<<af<<"\n";
            tr.upd_set(1,n-1,1,l,r-1);
            //cerr<<"after set:\n";
            //for(int i=1;i<=n;i++)cerr<<tr.fval(1,n-1,1,i,i).vpre<<" ";
           // cerr<<"\n";
            tr.upd(1,n-1,1,l-1,s-bf-curdifl);
            tr.upd(1,n-1,1,r,af-s-c*(r-l)-curdifr);
            //for(int i=1;i<=n;i++)cerr<<tr.fval(1,n-1,1,i,i).vpre<<" ";
            tr.upd_math(1,n-1,1,l,r-1,c);
            val.upd_set(1,n,1,l,r);
            val.upd_add(1,n,1,l,r,s);
            val.upd_math(1,n,1,l,r,c,l);
            //the gap may fluctuated in different ways depending on which index is bigger
        }else{
            int l,r;cin>>l>>r;
            cout<<tr.fval(1,n-1,1,l,r).mx+1<<"\n";
        }
        //cerr<<"AFTER EVERYTHING:\n";
        //for(int i=1;i<=n;i++)cerr<<tr.fval(1,n-1,1,i,i).vpre<<" ";
        //cerr<<"\n";
        //cerr<<tr.fval(1,n-1,1,1,n).mx<<"\n";
        //for(int i=1;i<=n;i++)cerr<<val.find(1,n,1,i)<<" ";
        //cerr<<"ALL\n";
        //cerr<<"\n";
    }
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 15
• Subtask 3: 0 / 35
• Subtask 4: 0 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17