Submission #265360

#	Time	Username	Problem	Language	Result	Execution time	Memory
265360		eohomegrownapps	Progression (NOI20_progression)	C++14	100 / 100	2805 ms	68440 KiB

Progression

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int deltas[400000];

struct Data{
    int len = 1;
    int maxpref=1;
    int maxsuff=1;
    ll prefval=0;
    ll suffval=0;
    int maxlen=1;
    ll deltasum = 0;
};

int n;
int ncnt=0;

Data combine(const Data &l, const Data &r){
    Data ans;
    ans.len = l.len + r.len;
    ans.deltasum = l.deltasum + r.deltasum;
    ans.maxpref = l.maxpref;
    ans.prefval = l.prefval;
    ans.maxsuff = r.maxsuff;
    ans.suffval = r.suffval;
    if (l.maxpref==l.len&&l.prefval==r.prefval){
        ans.maxpref=l.len+r.maxpref;
    }
    if (r.maxpref==r.len&&r.prefval==l.suffval){
        ans.maxsuff=r.len+l.maxsuff;
    }
    ans.maxlen=max(l.maxlen,r.maxlen);
    if (l.suffval==r.prefval){
        ans.maxlen=max(ans.maxlen,l.maxsuff+r.maxpref);
    }
    return ans;
}

Data initv(ll ind){
    Data ans;
    ans.prefval = deltas[ind];
    ans.suffval = deltas[ind];
    ans.deltasum = deltas[ind];
    return ans;
}

struct Node{
    int s,e;
    Data v;

    Node *l, *r;

    ll lazyval = 0;
    bool doreplace = false;

    Node(ll _s, ll _e){
        ncnt++;
        if (ncnt>2*n){
            while (true){continue;}
        }
        s=_s;e=_e;
        //cout<<s<<' '<<e<<'\n';
        if (s==e){
            v = initv(s);
            return;
        }
        int m = (s+e)/2;
        l = new Node(s,m);
        r = new Node(m+1,e);
        v = combine(l->v, r->v);
    }

    void propagate(){
        //cout<<"propagate "<<s<<' '<<e<<'\n';
        //cout<<"lazy: "<<lazyval<<' '<<doreplace<<'\n';
        if (doreplace){
            v.prefval = lazyval;
            v.suffval = lazyval;
            v.deltasum = v.len * lazyval;
            v.maxpref = v.len;
            v.maxsuff = v.len;
            v.maxlen = v.len;
        } else {
            v.prefval+=lazyval;
            v.suffval+=lazyval;
            v.deltasum+=v.len * lazyval;
        }
        if (s!=e){
            if (doreplace){
                l->doreplace = true;
                l->lazyval = lazyval;
                r->doreplace = true;
                r->lazyval = lazyval;
            } else {
                l->lazyval+=lazyval;
                r->lazyval+=lazyval;
            }
        }
        lazyval=0;
        doreplace=false;
    }

    Data query(ll a, ll b){
        assert(a<=b);
        assert(b<=n-2);
        int m = (s+e)/2;
        propagate();
        if (a==s&&b==e){
            return v;
        }
        if (b<=m){
            return l->query(a,b);
        } else if (m<a){
            return r->query(a,b);
        } else {
            return combine(l->query(a,m),r->query(m+1,b));
        }
    }

    void update(ll a, ll b, ll val, bool replace){
        assert(b<=n-2);
        int m = (s+e)/2;
        //cout<<"update "<<a<<' '<<b<<' '<<val<<' '<<replace<<'\n';
        assert(a<=b);
        if (a==s&&b==e){
            if (replace){
                doreplace=true;
                lazyval=val;
            } else {
                lazyval+=val;
            }
            return;
        }
        propagate();
        if (b<=m){
            l->update(a,b,val,replace);
        } else if (m<a){
            r->update(a,b,val,replace);
        } else {
            l->update(a,m,val,replace);
            r->update(m+1,b,val,replace);
        }
        l->propagate();
        r->propagate();
        v = combine(l->v,r->v);
    }
};

ll x0;
Node *root;

void patch(ll l, ll r, ll s, ll c){
    if (l==0){
        x0+=s;
    } else {
        root->update(l-1,l-1,s,false);
    }
    if (l<=r-1){
        root->update(l,r-1,c,false);
    }
    if (r!=n-1){
        root->update(r,r,-s-(r-l)*c,false);
    }
}

ll getDelta(ll ind){
    Data dxl = root->query(ind,ind);
    return dxl.deltasum;
}

ll getVal(ll ind){
    if (ind==0){
        return x0;
    }
    Data dxl = root->query(0,ind-1);
    ll ans = x0+dxl.deltasum;
    return ans;
}

void rewrite(ll l, ll r, ll s, ll c){
    ll xr1=0;
    if (r!=n-1){
        xr1 = getVal(r+1);
    }
    if (l==0){
        x0=s;
    } else {
        ll xlm1 = getVal(l-1);
        root->update(l-1,l-1,s-xlm1,true);
    }
    if (l<=r-1){
        root->update(l,r-1,c,true);
    }
    if (r!=n-1){
        root->update(r,r,xr1-s-(r-l)*c,true);
    }
}

ll evaluate(ll l, ll r){
    if (l==r){
        return 1;
    }
    Data d = root->query(l,r-1);
    return d.maxlen+1;
}

int main(){
    //cin.tie(0);
    //ios_base::sync_with_stdio(0);
    ll q;
    cin>>n>>q;
    cin>>x0;
    ll xprev = x0;
    for (ll i = 1; i<n; i++){
        ll xnew;
        cin>>xnew;
        deltas[i-1]=xnew-xprev;
        xprev=xnew;
    }
    root = new Node(0,n-1);
    /*for (ll i = 0; i<n-1; i++){
        cout<<getDelta(i)<<' ';
    }cout<<'\n';
    for (ll i = 0; i<n; i++){
        cout<<getVal(i)<<' ';
    }cout<<'\n';*/
    for (ll i = 0; i<q; i++){
        ll t;
        cin>>t;
        ll l,r,s,c;
        if (t==1){
            cin>>l>>r>>s>>c;
            patch(l-1,r-1,s,c);
            /*for (ll i = 0; i<n-1; i++){
                cout<<getDelta(i)<<' ';
            }cout<<'\n';
            for (ll i = 0; i<n; i++){
                cout<<getVal(i)<<' ';
            }cout<<'\n';*/
        } else if (t==2){
            cin>>l>>r>>s>>c;
            rewrite(l-1,r-1,s,c);
            /*for (ll i = 0; i<n-1; i++){
                cout<<getDelta(i)<<' ';
            }cout<<'\n';
            for (ll i = 0; i<n; i++){
                cout<<getVal(i)<<' ';
            }cout<<'\n';*/
        } else if (t==3){
            cin>>l>>r;
            cout<<evaluate(l-1,r-1)<<'\n';
        } else {
            continue;
        }
    }
}

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