Submission #1081527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081527		_callmelucian	Progression (NOI20_progression)	C++14	68 / 100	807 ms	104424 KiB

Progression

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct node {
    ll lazyAsgn, lazyAdd, sum;
    ll best, preLen, preVal, sufLen, sufVal, same, len;

    node() : lazyAsgn(0), lazyAdd(0), sum(0), best(0), preLen(0), preVal(0), sufLen(0), sufVal(0), same(0), len(0) {}

    void refine (node ln, node rn) {
        best = max({ln.best, rn.best, (ln.sufLen + rn.preLen) * (ln.sufVal == rn.preVal)});
        preLen = max(ln.preLen, (ln.len + rn.preLen) * (ln.same == rn.preVal));
        preVal = ln.preVal;
        sufLen = max(rn.sufLen, (ln.sufLen + rn.len) * (ln.sufVal == rn.same));
        sufVal = rn.sufVal;
        same = (ln.same == rn.same ? ln.same : LLONG_MAX);
        sum = ln.sum + rn.sum, len = ln.len + rn.len;
    }

    void applyAsgn (ll val, int l, int r) {
        lazyAsgn = val, lazyAdd = 0, sum = val * ll(r - l + 1);
        best = preLen = sufLen = r - l + 1;
        preVal = sufVal = same = val, len = r - l + 1;
    }

    void applyAdd (ll incr, int l, int r) {
        lazyAdd += incr, sum += incr * ll(r - l + 1);
        preVal += incr, sufVal += incr, len = r - l + 1;
        if (same != LLONG_MAX) same += incr;
    }

    void pushDown (node &ln, node &rn, int l, int r, int mid) {
        if (lazyAsgn != LLONG_MAX) {
            ln.applyAsgn(lazyAsgn, l, mid);
            rn.applyAsgn(lazyAsgn, mid + 1, r);
        }
        if (lazyAdd != 0) {
            ln.applyAdd(lazyAdd, l, mid);
            rn.applyAdd(lazyAdd, mid + 1, r);
        }
        lazyAsgn = LLONG_MAX, lazyAdd = 0;
    }
};

struct IT {
    vector<node> tr;
    IT (int sz) : tr(4 * sz) {}

    void rangeAssign (int a, int b, ll val, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            tr[k].applyAsgn(val, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
        rangeAssign(a, b, val, 2 * k, l, mid);
        rangeAssign(a, b, val, 2 * k + 1, mid + 1, r);
        tr[k].refine(tr[2 * k], tr[2 * k + 1]);
    }

    void rangeAdd (int a, int b, ll incr, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            tr[k].applyAdd(incr, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
        rangeAdd(a, b, incr, 2 * k, l, mid);
        rangeAdd(a, b, incr, 2 * k + 1, mid + 1, r);
        tr[k].refine(tr[2 * k], tr[2 * k + 1]);
    }

    ll querySum (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return tr[k].sum;
        int mid = (l + r) >> 1;
        tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
        return querySum(a, b, 2 * k, l, mid) + querySum(a, b, 2 * k + 1, mid + 1, r);
    }

    node query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return node();
        if (a <= l && r <= b) return tr[k];
        int mid = (l + r) >> 1;
        tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
        node ans; ans.refine(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
        return ans;
    }

    ll longestSame (int a, int b, int k, int l, int r) {
        return query(a, b, k, l, r).best;
    }

    void lineAssign (int a, int b, ll S, ll C, int k, int l, int r) {
        if (b < r) {
            ll incrR = querySum(1, b + 1, k, l, r) - S + ll(b - a) * C;
            rangeAssign(b + 1, b + 1, incrR, k, l, r);
        }
        ll incrL = S - (a == l ? 0 : querySum(1, a - 1, k, l, r));
        rangeAssign(a, a, incrL, k, l, r);
        if (a < b) rangeAssign(a + 1, b, C, k, l, r);
    }

    void lineAdd (int a, int b, ll S, ll C, int k, int l, int r) {
        if (b < r)
            rangeAdd(b + 1, b + 1, -(S + ll(b - a) * C), k, l, r);
        rangeAdd(a, a, S, k, l, r);
        if (a < b) rangeAdd(a + 1, b, C, k, l, r);
    }
};

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

    int n, q; cin >> n >> q;
    IT tree(n);

    for (int i = 1; i <= n; i++) {
        int D; cin >> D;
        tree.lineAssign(i, i, D, 0, 1, 1, n);
    }

    while (q--) {
        int type, L, R; cin >> type >> L >> R;
        if (type == 1) {
            int S, C; cin >> S >> C;
            tree.lineAdd(L, R, S, C, 1, 1, n);
        }
        else if (type == 2) {
            int S, C; cin >> S >> C;
            tree.lineAssign(L, R, S, C, 1, 1, n);
        }
        else {
            if (L == R) cout << 1 << "\n";
            else cout << tree.longestSame(L + 1, R, 1, 1, n) + 1 << "\n";
        }
    }

    return 0;
}

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