Submission #1217393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217393		ProtonDecay314	Progression (NOI20_progression)	C++20	100 / 100	1225 ms	98152 KiB

Progression

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

/*
is_id - is identity
lp - longest prefix
lpv - longest prefix value
ls - longest suffix
lsv - longest suffix value
lng - longest
lngv - longest value
*/
struct DiffTreeState {
    bool is_id;
    int l, r;
    int lp;
    ll lpv;
    int ls;
    ll lsv; 
    int lng;
    ll lngv;

    DiffTreeState(bool a_is_id, int a_l, int a_r, int a_lp, ll a_lpv, int a_ls, ll a_lsv, int a_lng, ll a_lngv): is_id(a_is_id), l(a_l), r(a_r), lp(a_lp), lpv(a_lpv), ls(a_ls), lsv(a_lsv),  lng(a_lng), lngv(a_lngv) {};
};

const DiffTreeState DIFF_TREE_STATE_ID = {true, 0, 0, 0, 0ll, 0, 0ll, 0, 0ll};

inline DiffTreeState combine_state(DiffTreeState s1, DiffTreeState s2) {
    if(s1.is_id) return {s2.is_id, s2.l, s2.r, s2.lp, s2.lpv, s2.ls, s2.lsv, s2.lng, s2.lngv};
    if(s2.is_id) return {s1.is_id, s1.l, s1.r, s1.lp, s1.lpv, s1.ls, s1.lsv, s1.lng, s1.lngv};

    int lp;
    ll lpv;
    int ls;
    ll lsv; 
    int lng;
    ll lngv;

    lp = s1.lp;
    lpv = s1.lpv;

    if(s1.lp == (s1.r - s1.l + 1) && s1.lpv == s2.lpv) {
        lp += s2.lp;
    }

    ls = s2.ls;
    lsv = s2.lsv;

    if(s2.ls == (s2.r - s2.l + 1) && s1.lsv == s2.lsv) {
        ls += s1.ls;
    }

    lng = s1.lng;
    lngv = s1.lngv;

    if(s2.lng > lng) {
        lng = s2.lng;
        lngv = s2.lngv;
    }

    if(s1.lsv == s2.lpv && s1.ls + s2.lp > lng) {
        lng = s1.ls + s2.lp;
        lngv = s1.lsv;
    }

    return {false, s1.l, s2.r, lp, lpv, ls, lsv, lng, lngv};
}

struct DiffTree {
    DiffTree *lt, *rt;
    DiffTreeState v;

    bool marked_inc, marked_set;
    ll lazy;

    DiffTree(int a_l, int a_r): lt(nullptr), rt(nullptr), v({true, a_l, a_r, 0ll, 0ll, 0ll, 0ll, 0ll, 0ll}), marked_inc(false), marked_set(false), lazy(0ll) {};

    void combine() {
        v = combine_state(lt->v, rt->v);
    }

    void push() {
        if((!marked_inc) && (!marked_set)) return;

        if(v.l == v.r) {
            marked_inc = marked_set = false;
            lazy = 0ll;

            return;
        }

        if(marked_inc) {
            /*
            marked for increment
            */
            if(lt->marked_set) {
                lt->marked_set = true;
                lt->lazy += lazy;
                lt->v.lngv += lazy;
                lt->v.lsv += lazy;
                lt->v.lpv += lazy;
            } else {
                lt->marked_inc = true;
                lt->lazy += lazy;
                lt->v.lngv += lazy;
                lt->v.lsv += lazy;
                lt->v.lpv += lazy;
            }

            if(rt->marked_set) {
                rt->marked_set = true;
                rt->lazy += lazy;
                rt->v.lngv += lazy;
                rt->v.lsv += lazy;
                rt->v.lpv += lazy;
            } else {
                rt->marked_inc = true;
                rt->lazy += lazy;
                rt->v.lngv += lazy;
                rt->v.lsv += lazy;
                rt->v.lpv += lazy;
            }
        } else {
            /*
            marked for assignment
            */

            lt->marked_inc = false;
            lt->marked_set = true;
            lt->lazy = lazy;
            lt->v.lng = lt->v.ls = lt->v.lp = lt->v.r - lt->v.l + 1;
            lt->v.lngv = lt->v.lsv = lt->v.lpv = lazy;

            rt->marked_inc = false;
            rt->marked_set = true;
            rt->lazy = lazy;
            rt->v.lng = rt->v.ls = rt->v.lp = rt->v.r - rt->v.l + 1;
            rt->v.lngv = rt->v.lsv = rt->v.lpv = lazy;
        }

        marked_inc = marked_set = false;
        lazy = 0ll;
    }

    void build(const vll& a) {
        if(v.l == v.r) {
            DiffTreeState nv = {false, v.l, v.r, 1, a[v.l], 1, a[v.l], 1, a[v.l]};
            v = nv;
            return;
        }
        
        int m = (v.l + v.r) >> 1;
        
        lt = new DiffTree(v.l, m);
        rt = new DiffTree(m + 1, v.r);
        
        lt->build(a);
        rt->build(a);
        
        combine();
        // cerr << "! " << v.l << " " << v.r << " " << v.lngv << endl;
    }

    void range_inc(int ql, int qr, ll inc) {
        if(ql > v.r || qr < v.l) return;

        push();

        if(ql == v.l && qr == v.r) {
            marked_inc = true;
            lazy = inc;
            v.lngv += inc;
            v.lsv += inc;
            v.lpv += inc;

            return;
        }

        int m = (v.l + v.r) >> 1;

        lt->range_inc(ql, min(qr, m), inc);
        rt->range_inc(max(ql, m + 1), qr, inc);

        combine();
    }

    void range_set(int ql, int qr, ll inc) {
        if(ql > v.r || qr < v.l) return;

        push();

        if(ql == v.l && qr == v.r) {
            marked_set = true;
            lazy = inc;
            v.lngv = v.lsv = v.lpv = inc;
            v.lng = v.ls = v.lp = v.r - v.l + 1;

            return;
        }

        int m = (v.l + v.r) >> 1;

        lt->range_set(ql, min(qr, m), inc);
        rt->range_set(max(ql, m + 1), qr, inc);

        combine();
    }

    DiffTreeState range_qry(int ql, int qr) {
        if(ql > v.r || qr < v.l) return DIFF_TREE_STATE_ID;

        push();

        if(ql == v.l && qr == v.r) return v;

        int m = (v.l + v.r) >> 1;

        return combine_state(lt->range_qry(ql, min(qr, m)), rt->range_qry(max(ql, m + 1), qr));
    }

    ll qry_pt(int i) {
        push();

        if(v.l == v.r && v.l == i) {
            // cerr << "qrypt: " << v.l << " " << v.r << " " << i << " " << v.lngv << " " << v.lpv << " " << v.lsv << " " << v.lng << endl;
            return v.lngv;
        }
    
        int m = (v.l + v.r) >> 1;

        if(i <= m) return lt->qry_pt(i);
        else return rt->qry_pt(i);
    }

    void printv() {
        for(int i = v.l; i <= v.r; i++) {
            cerr << qry_pt(i) << " ";
        }
        cerr << endl;
    }
};

struct Tree {
    Tree *lt, *rt;
    int l, r;
    ll v;
    bool marked_inc, marked_set;
    ll lazy_b0, lazy_m0;

    Tree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v(0ll), marked_inc(false), marked_set(false), lazy_b0(0ll), lazy_m0(0ll) {};

    void push() {
        if((!marked_inc) && (!marked_set)) return;

        if(l == r) {
            marked_inc = marked_set = false;
            lazy_b0 = lazy_m0 = 0ll;
            return;
        }

        if(marked_inc) {
            if(lt->marked_set) {
                lt->marked_set = true;
                lt->lazy_b0 += lazy_b0;
                lt->lazy_m0 += lazy_m0;
                lt->v += lazy_b0;
            } else {
                lt->marked_inc = true;
                lt->lazy_b0 += lazy_b0;
                lt->lazy_m0 += lazy_m0;
                lt->v += lazy_b0;
            }

            if(rt->marked_set) {
                rt->marked_set = true;
                rt->lazy_b0 += lazy_b0 + lazy_m0 * ((ll)lt->r - (ll)lt->l + 1ll);
                rt->lazy_m0 += lazy_m0;
                rt->v += lazy_b0 + lazy_m0 * ((ll)lt->r - (ll)lt->l + 1ll);
            } else {
                rt->marked_inc = true;
                rt->lazy_b0 += lazy_b0 + lazy_m0 * ((ll)lt->r - (ll)lt->l + 1ll);
                rt->lazy_m0 += lazy_m0;
                rt->v += lazy_b0 + lazy_m0 * ((ll)lt->r - (ll)lt->l + 1ll);
            }
        } else {
            lt->marked_set = true;
            lt->marked_inc = false;
            lt->lazy_b0 = lazy_b0;
            lt->lazy_m0 = lazy_m0;
            lt->v = lazy_b0;

            rt->marked_set = true;
            rt->marked_inc = false;
            rt->lazy_b0 = lazy_b0 + lazy_m0 * ((ll)lt->r - (ll)lt->l + 1ll);
            rt->lazy_m0 = lazy_m0;
            rt->v = lazy_b0 + lazy_m0 * ((ll)lt->r - (ll)lt->l + 1ll);
        }

        marked_inc = marked_set = false;
        lazy_b0 = lazy_m0 = 0ll;
    }

    void build(const vll& a) {
        if(l == r) {
            v = a[l];
            return;
        }
        int m = (l + r) >> 1;

        lt = new Tree(l, m);
        rt = new Tree(m + 1, r);

        lt->build(a);
        rt->build(a);

        // ! No need to combine for this segtree
    }

    void patch(int ql, int qr, ll s, ll c) {
        if(ql > r || qr < l) return;

        push();

        if(ql == l && qr == r) {
            marked_inc = true;
            lazy_b0 += s;
            lazy_m0 += c;
            v += s;
            return;
        }

        int m = (l + r) >> 1;

        lt->patch(ql, min(qr, m), s, c);

        ll effective_ind = max(0ll, (ll)m + 1ll - (ll)ql);
        rt->patch(max(ql, m + 1), qr, s + c * effective_ind, c);
    }

    void rewrite(int ql, int qr, ll s, ll c) {
        if(ql > r || qr < l) return;

        push();

        if(ql == l && qr == r) {
            marked_set = true;
            lazy_b0 = s;
            lazy_m0 = c;
            v = s;
            return;
        }

        int m = (l + r) >> 1;

        lt->rewrite(ql, min(qr, m), s, c);

        ll effective_ind = max(0ll, (ll)m + 1ll - (ll)ql);
        rt->rewrite(max(ql, m + 1), qr, s + c * effective_ind, c);
    }

    ll qry(ll i) {
        push();
        if(l == r && i == l) return v;

        ll m = (l + r) >> 1ll;

        if(i <= m) return lt->qry(i);
        else return rt->qry(i);
    }

    void printv() {
        for(ll i = l; i <= r; i++) {
            cerr << qry(i) << " ";
        }
        cerr << endl;
    }

    ll longest_chain_brute(ll l, ll r) {
        if(r - l + 1ll <= 2ll) return r - l + 1ll;

        vll vals(r - l + 1ll, 0ll);

        for(ll i = l; i <= r; i++) {
            vals[i - l] = qry(i);
        }

        ll prev_diff = INF(ll);
        ll cur_run = 1ll;
        ll ans = 0ll;

        for(ll i = l; i < r; i++) {
            if(vals[i - l + 1ll] - vals[i - l] == prev_diff) {
                cur_run++;
                ans = max(ans, cur_run);
            } else {
                cur_run = 1ll;
                prev_diff = vals[i - l + 1ll] - vals[i - l];
                ans = max(ans, cur_run);
            }
        }

        return ans + 1ll;
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;

    vll d(n, 0ll);

    for(ll& v : d) cin >> v;

    Tree tr(0ll, n - 1ll);
    tr.build(d);

    for(int i = n - 1; i >= 1; i--) {
        d[i] = d[i] - d[i - 1];
    }

    DiffTree dtr(0ll, n - 1ll);
    dtr.build(d);

    // cerr << "root: " << dtr.v.l << " " << dtr.v.r << " " << dtr.v.lngv << " " << dtr.qry_pt(0) << endl;
    // cerr << "root: " << dtr.v.l << " " << dtr.v.r << " " << dtr.v.lngv << " " << dtr.qry_pt(0) << endl;

    // for(int i = 0; i < n; i++) {
    //     cerr << dtr.range_qry(i, i).lngv << " ";
    // }

    // cerr << endl;

    while(q--) {
        int qtype;
        cin >> qtype;

        if(qtype == 1) {
            /*
            Patch (range increment)
            */
            int l, r;
            ll s, c;
            cin >> l >> r >> s >> c;
            l--; r--;

            tr.patch(l, r, s, c);
            if(l + 1 <= r) dtr.range_inc(l + 1, r, c);
            dtr.range_set(l, l, tr.qry(l) - (l == 0 ? 0 : tr.qry(l - 1)));
            if(r + 1 < n) dtr.range_set(r + 1, r + 1, tr.qry(r + 1) - (r + 1 == 0 ? 0 : tr.qry(r)));
            // tr.printv();

            // dtr.printv();
        } else if (qtype == 2) {
            /*
            Rewrite (range assignment)
            */
            int l, r;
            ll s, c;
            cin >> l >> r >> s >> c;
            l--; r--;

            tr.rewrite(l, r, s, c);
            if(l + 1 <= r) dtr.range_set(l + 1, r, c);
            dtr.range_set(l, l, tr.qry(l) - (l == 0 ? 0 : tr.qry(l - 1)));
            if(r + 1 < n) dtr.range_set(r + 1, r + 1, tr.qry(r + 1) - (r + 1 == 0 ? 0 : tr.qry(r)));
            // tr.printv();

            // dtr.printv();
        } else {
            int l, r;
            cin >> l >> r;
            l--; r--;
            /*
            Evaluate
            */

            if(r - l + 1 <= 2) cout << r - l + 1 << "\n";
            else {
                cout << dtr.range_qry(l + 1, r).lng + 1 << "\n";
            }
        }
    }

    cout << flush;

    return 0;
}

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