oj.uz

답안 #265301

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
265301 2020-08-14T15:06:46 Z eohomegrownapps Progression (NOI20_progression) C++14
0 / 100
 1191 ms 1048580 KB 
#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){
    if (l==0){
        x0=s;
    } else {
        ll xlm1 = getVal(l-1);
        root->update(l-1,l-1,s-xlm1,true);
    }
    root->update(l,r-1,c,true);
    if (r!=n-1){
        ll xr1 = getVal(r+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-2);
    /*for (ll i = 0; i<n-1; i++){
        ll d = getDelta(i);
        cout<<"d at "<<i<<": "<<d<<'\n';
    }
    for (ll i = 0; i<n; i++){
        ll v = getVal(i);
        cout<<"v at "<<i<<": "<<v<<'\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);
        } else if (t==2){
            cin>>l>>r>>s>>c;
            rewrite(l-1,r-1,s,c);
        } else if (t==3){
            cin>>l>>r;
            cout<<evaluate(l-1,r-1)<<'\n';
        } else {
            continue;
        }
        /*for (ll i = 0; i<n-1; i++){
            ll d = getDelta(i);
            cout<<"d at "<<i<<": "<<d<<'\n';
        }
        for (ll i = 0; i<n; i++){
            ll v = getVal(i);
            cout<<"v at "<<i<<": "<<v<<'\n';
        }*/
    }
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 78444 KB Output is correct
2 Correct 126 ms 632 KB Output is correct
3 Correct 100 ms 632 KB Output is correct
4 Correct 106 ms 760 KB Output is correct
5 Correct 101 ms 760 KB Output is correct
6 Correct 99 ms 760 KB Output is correct
7 Correct 117 ms 700 KB Output is correct
8 Runtime error 695 ms 1048580 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 484 ms 82616 KB Output is correct
2 Correct 103 ms 3064 KB Output is correct
3 Correct 104 ms 3064 KB Output is correct
4 Correct 96 ms 3180 KB Output is correct
5 Correct 116 ms 3264 KB Output is correct
6 Correct 104 ms 3192 KB Output is correct
7 Correct 110 ms 3192 KB Output is correct
8 Runtime error 653 ms 1048580 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1191 ms 85316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 484 ms 82616 KB Output is correct
2 Correct 103 ms 3064 KB Output is correct
3 Correct 104 ms 3064 KB Output is correct
4 Correct 96 ms 3180 KB Output is correct
5 Correct 116 ms 3264 KB Output is correct
6 Correct 104 ms 3192 KB Output is correct
7 Correct 110 ms 3192 KB Output is correct
8 Runtime error 653 ms 1048580 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 78444 KB Output is correct
2 Correct 126 ms 632 KB Output is correct
3 Correct 100 ms 632 KB Output is correct
4 Correct 106 ms 760 KB Output is correct
5 Correct 101 ms 760 KB Output is correct
6 Correct 99 ms 760 KB Output is correct
7 Correct 117 ms 700 KB Output is correct
8 Runtime error 695 ms 1048580 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -