Submission #892548

#	Time	Username	Problem	Language	Result	Execution time	Memory
892548		CDuong	Progression (NOI20_progression)	C++17	100 / 100	640 ms	100044 KiB

Progression

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 3e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

struct SegmentTree {
    struct node {
        i64 val = 0;
        int same = 0, len = 0;
        pair<int, int> pfx, sfx;
        i64 lz_mul = 1, lz_add = 0;

        node() {}
        node(int val) : val(val), same(1), len(1), pfx({val, 1}), sfx({val, 1}) {}
        
        node operator + (const node &rhs) {
            node res;
            res.val = val + rhs.val;
            res.len = len + rhs.len;
            res.same = max(same, rhs.same);
            if (sfx.ff == rhs.pfx.ff) res.same = max(res.same, sfx.ss + rhs.pfx.ss);
            res.pfx = pfx, res.sfx = rhs.sfx;
            if (pfx.ss == len and pfx.ff == rhs.pfx.ff) res.pfx = {pfx.ff, pfx.ss + rhs.pfx.ss};
            if (rhs.sfx.ss == rhs.len and sfx.ff == rhs.sfx.ff) res.sfx = {rhs.sfx.ff, rhs.sfx.ss + sfx.ss};
            // cout << *this << endl << rhs << endl << res << endl << endl;
            return res;
        }

        friend ostream & operator << (ostream &out, node o) {
            return out << o.pfx.ff << " " << o.pfx.ss << " " << o.sfx.ff << " " << o.sfx.ss << " " << o.same;
        }
    };

    int n;
    vector<node> data;

    SegmentTree(int n, vector<int> &diff) : n(n), data(4 * n + 10) {
        auto build = [&](auto build, int l, int r, int idx) -> void {
            if (l == r) {
                data[idx] = node(diff[l]);
                return;
            }
            int mid = (l + r) >> 1;
            build(build, l, mid, idx << 1);
            build(build, mid + 1, r, idx << 1 | 1);
            data[idx] = data[idx << 1] + data[idx << 1 | 1];
        };
        build(build, 1, n, 1);
    };

    void apply(int idx, i64 mul, i64 add) {
        if (mul == 0) {
            data[idx].val = add * data[idx].len;
            data[idx].same = data[idx].len;
            data[idx].pfx = data[idx].sfx = {add, data[idx].len};
            data[idx].lz_mul = mul, data[idx].lz_add = add;
        }
        else {
            data[idx].val += add * data[idx].len;
            data[idx].pfx.ff += add, data[idx].sfx.ff += add;
            data[idx].lz_add += add;
        }
    }

    void down(int idx) {
        apply(idx << 1, data[idx].lz_mul, data[idx].lz_add);
        apply(idx << 1 | 1, data[idx].lz_mul, data[idx].lz_add);
        data[idx].lz_add = 0, data[idx].lz_mul = 1;
    }

    void update(int l, int r, int idx, int u, int v, i64 mul, i64 add) {
        if (u <= l && r <= v) {
            apply(idx, mul, add);
            return;
        }
        down(idx);
        int mid = (l + r) >> 1;
        if (u <= mid) update(l, mid, idx << 1, u, v, mul, add);
        if (mid + 1 <= v) update(mid + 1, r, idx << 1 | 1, u, v, mul, add);
        data[idx] = data[idx << 1] + data[idx << 1 | 1];
    }

    void update(int u, int v, i64 mul, i64 add) {
        update(1, n, 1, u, v, mul, add);
    }

    node get(int l, int r, int idx, int u, int v) {
        if (u <= l && r <= v) return data[idx];
        down(idx);
        int mid = (l + r) >> 1;
        if (v <= mid) return get(l, mid, idx << 1, u, v);
        if (mid + 1 <= u) return get(mid + 1, r, idx << 1 | 1, u, v);
        return get(l, mid, idx << 1, u, v) + get(mid + 1, r, idx << 1 | 1, u, v);
    }

    node get(int u, int v) {
        return get(1, n, 1, u, v);
    }
};

int n, q;
int a[mxN];
vector<int> diff;

void solve() {
    cin >> n >> q;
    diff.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        diff[i] = a[i] - a[i - 1];
    }
    SegmentTree st(n, diff);
    // cout << st.data[1].same << endl;
    while (q--) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int l, r, s, c;
            cin >> l >> r >> s >> c;
            st.update(l, l, 1, s);
            if (l < r) st.update(l + 1, r, 1, c);
            if (r + 1 <= n) st.update(r + 1, r + 1, 1, -(1ll * c * (r - l) + s));
        }
        else if (tp == 2) {
            int l, r, s, c;
            cin >> l >> r >> s >> c;
            i64 cl = st.get(1, l).val;
            if (r + 1 <= n) {
                i64 cr1 = st.get(1, r + 1).val;
                st.update(r + 1, r + 1, 0, cr1 - (s + (r - l) * c));
            }
            st.update(l, l, 1, s - cl);
            if (l < r) st.update(l + 1, r, 0, c);
        }
        else {
            int l, r;
            cin >> l >> r;
            if (l == r) cout << 1 << "\n";
            else cout << st.get(l + 1, r).same + 1 << "\n";
        }
    }
    // for (int i = 1; i <= n; ++i)
    //     cout << st.get(1, i).val << " \n"[i == n];
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   // auto end = chrono::high_resolution_clock::now();
   // cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   // cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   // cout << "Check array size pls sir" << endl;
#endif

}

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