Submission #265365

#	Time	Username	Problem	Language	Result	Execution time	Memory
265365		eohomegrownapps	Progression (NOI20_progression)	C++14	100 / 100	2867 ms	79596 KiB

Progression

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll deltas[300000];
 
struct Data{
    ll len = 1;
    ll maxpref=1;
    ll maxsuff=1;
    ll prefval=0;
    ll suffval=0;
    ll maxlen=1;
    ll deltasum = 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 init(ll ind){
    Data ans;
    ans.prefval = deltas[ind];
    ans.suffval = deltas[ind];
    ans.deltasum = deltas[ind];
    return ans;
}
 
struct Node{
    ll s,e,m;
    Data v;
 
    Node *l, *r;
 
    ll lazyval = 0;
    bool doreplace = false;
 
    Node(ll _s, ll _e){
        s=_s;e=_e;
        //cout<<s<<' '<<e<<'\n';
        if (s==e){
            v = init(s);
            return;
        }
        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){
        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 {
            Data dl = l->query(a,m);
            Data dr = r->query(m+1,b);
            //cout<<"combine "<<a<<' '<<m<<' '<<dl.deltasum<<'\n';
            //cout<<"combine "<<m+1<<' '<<b<<' '<<dr.deltasum<<'\n';
            Data c = combine(dl,dr);
            //cout<<"ans: "<<c.deltasum<<'\n';
            return c;
        }
    }
 
    void update(ll a, ll b, ll val, bool replace){
        //cout<<"update "<<a<<' '<<b<<' '<<val<<' '<<replace<<'\n';
        if (a>b){return;}
        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,n;
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);
    }
    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 xlm1, xr1;
    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;
        }
    }
}

Compilation message (stderr)

Progression.cpp: In function 'void rewrite(ll, ll, ll, ll)':
Progression.cpp:174:8: warning: unused variable 'xlm1' [-Wunused-variable]
  174 |     ll xlm1, xr1;
      |        ^~~~
Progression.cpp:188:29: warning: 'xr1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  188 |         root->update(r,r,xr1-s-(r-l)*c,true);
      |                          ~~~^~

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