Submission #1235503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235503		Gabp	Progression (NOI20_progression)	C++20	100 / 100	1175 ms	89052 KiB

Progression

#include<bits/stdc++.h>
using namespace std;

// actual values
struct SegTree {
    vector<long long int> add1, add2; // constant, difference
    vector<long long int> val; // set
    vector<bool> lazy; // true if set

    SegTree(int n, vector<long long int> &a) {
        add1.assign(4 * n, 0);
        add2.assign(4 * n, 0);
        val.resize(4 * n);
        lazy.assign(4 * n, false);

        build(1, 0, n - 1, a);
    }

    void build(int v, int tl, int tr, vector<long long int> &a) {
        if (tl == tr) {
            val[v] = a[tl];
            lazy[v] = true;
            return;
        }

        int mid = tl + (tr - tl) / 2;
        build(2 * v, tl, mid, a);
        build(2 * v + 1, mid + 1, tr, a);
    }

    int push(int v, int tl, int tr) {
        int mid = tl + (tr - tl) / 2;
        if (lazy[v]) {
            val[2 * v] = val[v];
            val[2 * v + 1] = val[v];
            add1[2 * v] = add1[2 * v + 1] = 0;
            add2[2 * v] = add2[2 * v + 1] = 0;
            lazy[v] = false;
            lazy[2 * v] = true;
            lazy[2 * v + 1] = true;
        }

        add1[2 * v] += add1[v];
        add1[2 * v + 1] += add1[v] + (mid + 1 - tl) * add2[v];
        add2[2 * v] += add2[v];
        add2[2 * v + 1] += add2[v];
        add1[v] = add2[v] = 0;
        return mid;
    }

    // affine add
    void update1(int v, int tl, int tr, int l, int r, long long int start, long long int diff) {
        if (l > r) return;
        if (tl == l && tr == r) {
            add1[v] += start;
            add2[v] += diff;
            return;
        }

        int mid = push(v, tl, tr);
        update1(2 * v, tl, mid, l, min(mid, r), start, diff);
        int cnt = max(0, mid + 1 - l);
        update1(2 * v + 1, mid + 1, tr, max(mid + 1, l), r, start + cnt * diff, diff);
    }

    // range set
    void update2(int v, int tl, int tr, int l, int r, long long int x) {
        if (l > r) return;
        if (tl == l && tr == r) {
            add1[v] = 0;
            add2[v] = 0;
            lazy[v] = true;
            val[v] = x;
            return;
        }

        int mid = push(v, tl, tr);
        update2(2 * v, tl, mid, l, min(mid, r), x);
        update2(2 * v + 1, mid + 1, tr, max(mid + 1, l), r, x);
    }

    long long int query(int v, int tl, int tr, int idx) {
        if (tl == tr) return val[v] + add1[v];

        int mid = push(v, tl, tr);
        if (idx <= mid) return query(2 * v, tl, mid, idx);
        else return query(2 * v + 1, mid + 1, tr, idx);
    }
};

struct Data {
    int ans, sz;
    long long int lDiff, rDiff;
    int lCnt, rCnt;
};

Data merge(Data l, Data r) {
    if (l.sz == 0) return r;
    if (r.sz == 0) return l;

    Data res;
    res.sz = l.sz + r.sz;
    res.ans = max(l.ans, r.ans);

    res.lDiff = l.lDiff;
    res.lCnt = l.lCnt + (l.lCnt == l.sz && r.lDiff == l.lDiff ? r.lCnt : 0);
    res.rDiff = r.rDiff;
    res.rCnt = r.rCnt + (r.rCnt == r.sz && l.rDiff == r.rDiff ? l.rCnt : 0);

    if (l.rDiff == r.lDiff) res.ans = max(res.ans, l.rCnt + r.lCnt);
    return res;
}

struct SegTree2 {
    vector<Data> st;
    vector<long long int> add; // add
    vector<long long int> val; // set
    vector<bool> lazy;

    SegTree2(int n, vector<long long int> &a) {
        st.resize(4 * n);
        add.assign(4 * n, 0);
        val.resize(4 * n);
        lazy.assign(4 * n, false);

        build(1, 0, n - 1, a);
    }

    void build(int v, int tl, int tr, vector<long long int> &a) {
	    if (tl > tr) return;
        if (tl == tr) {
            st[v].sz = st[v].ans = st[v].lCnt = st[v].rCnt = 1;
            st[v].lDiff = st[v].rDiff = a[tl + 1] - a[tl];
            return;
        }

        int mid = tl + (tr - tl) / 2;
        build(2 * v, tl, mid, a);
        build(2 * v + 1, mid + 1, tr, a);
        st[v] = merge(st[2 * v], st[2 * v + 1]);
    }

    void push(int v) {
        if (lazy[v]) {
            st[2 * v].ans = st[2 * v].lCnt = st[2 * v].rCnt = st[2 * v].sz;
            st[2 * v].lDiff = st[2 * v].rDiff = val[v];
            st[2 * v + 1].ans = st[2 * v + 1].lCnt = st[2 * v + 1].rCnt = st[2 * v + 1].sz;
            st[2 * v + 1].lDiff = st[2 * v + 1].rDiff = val[v];
            val[2 * v] = val[2 * v + 1] = val[v];
            add[2 * v] = add[2 * v + 1] = 0;
            lazy[v] = false;
            lazy[2 * v] = lazy[2 * v + 1] = true;
        }

        st[2 * v].lDiff += add[v];
        st[2 * v].rDiff += add[v];
        st[2 * v + 1].lDiff += add[v];
        st[2 * v + 1].rDiff += add[v];
        add[2 * v] += add[v];
        add[2 * v + 1] += add[v];
        add[v] = 0;
    }

    // range add
    void update1(int v, int tl, int tr, int l, int r, long long int x) {
        if (l > r) return;
        if (tl == l && tr == r) {
            add[v] += x;
            st[v].lDiff += x;
            st[v].rDiff += x;
            return;
        }

        push(v);
        int mid = tl + (tr - tl) / 2;
        update1(2 * v, tl, mid, l, min(mid, r), x);
        update1(2 * v + 1, mid + 1, tr, max(mid + 1, l), r, x);
        st[v] = merge(st[2 * v], st[2 * v + 1]);
    }

    // range set
    void update2(int v, int tl, int tr, int l, int r, long long int x) {
        if (l > r) return;
        if (tl == l && tr == r) {
            add[v] = 0;
            lazy[v] = true;
            val[v] = x;
            st[v].ans = st[v].lCnt = st[v].rCnt = st[v].sz;
            st[v].lDiff = st[v].rDiff = x;
            return;
        }

        push(v);
        int mid = tl + (tr - tl) / 2;
        update2(2 * v, tl, mid, l, min(mid, r), x);
        update2(2 * v + 1, mid + 1, tr, max(mid + 1, l), r, x);
        st[v] = merge(st[2 * v], st[2 * v + 1]);
    }

    Data query(int v, int tl, int tr, int l, int r) {
        if (l > r) {
            Data res;
            res.sz = res.ans = 0;
            return res;
        }

        if (tl == l && tr == r) return st[v];

        push(v);
        int mid = tl + (tr - tl) / 2;
        return merge(
            query(2 * v, tl, mid, l, min(mid, r)),
            query(2 * v + 1, mid + 1, tr, max(mid + 1, l), r)
        );
    }
};

void solve() {
    int n,q; cin >> n >> q;
    vector<long long int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    SegTree st1(n, a);
    SegTree2 st2(n - 1, a);

    while (q--) {
        int t; cin >> t;
        int l,r; cin >> l >> r;
        l--; r--;
        if (t == 1) {
            long long int s,c; cin >> s >> c;
            st1.update1(1, 0, n - 1, l, r, s, c);

            if (l) {
                long long int val1 = st1.query(1, 0, n - 1, l - 1);
                long long int val2 = st1.query(1, 0, n - 1, l);
                st2.update2(1, 0, n - 2, l - 1, l - 1, val2 - val1);
            }
            if (r + 1 < n) {
                long long int val1 = st1.query(1, 0, n - 1, r);
                long long int val2 = st1.query(1, 0, n - 1, r + 1);
                st2.update2(1, 0, n - 2, r, r, val2 - val1);
            }
            st2.update1(1, 0, n - 2, l, r - 1, c);
        } else if (t == 2) {
            long long int s,c; cin >> s >> c;
            st1.update2(1, 0, n - 1, l, r, s);
            st1.update1(1, 0, n - 1, l, r, 0, c);

            if (l) {
                long long int val1 = st1.query(1, 0, n - 1, l - 1);
                long long int val2 = st1.query(1, 0, n - 1, l);
                st2.update2(1, 0, n - 2, l - 1, l - 1, val2 - val1);
            }
            if (r + 1 < n) {
                long long int val1 = st1.query(1, 0, n - 1, r);
                long long int val2 = st1.query(1, 0, n - 1, r + 1);
                st2.update2(1, 0, n - 2, r, r, val2 - val1);
            }
            st2.update2(1, 0, n - 2, l, r - 1, c);
        } else {
            Data res = st2.query(1, 0, n - 2, l, r - 1);
            cout << res.ans + 1 << '\n';
        }
    }
}

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

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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