Submission #1181880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181880		mehmetkagan	Progression (NOI20_progression)	C++20	0 / 100	621 ms	141708 KiB

Progression

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

struct SegA {
    int n;
    vector<ll> base;
    vector<bool> lazySet;
    vector<ll> lazySetA, lazySetB, lazyAddA, lazyAddB;
    SegA(int n, const vector<ll>& init): n(n), base(init) {
        lazySet.assign(4*n, false);
        lazySetA.assign(4*n, 0);
        lazySetB.assign(4*n, 0);
        lazyAddA.assign(4*n, 0);
        lazyAddB.assign(4*n, 0);
    }
    void pushDown(int idx, int l, int r) {
        int m = (l+r)/2, lc = idx*2, rc = idx*2+1;
        if(lazySet[idx]){
            lazySet[lc] = lazySet[rc] = true;
            lazySetA[lc] = lazySetA[idx];
            lazySetB[lc] = lazySetB[idx];
            lazySetA[rc] = lazySetA[idx];
            lazySetB[rc] = lazySetB[idx];
            lazyAddA[lc] = lazyAddB[lc] = 0;
            lazyAddA[rc] = lazyAddB[rc] = 0;
            lazySet[idx] = false;
            lazySetA[idx] = lazySetB[idx] = 0;
        }
        if(lazyAddA[idx] != 0 || lazyAddB[idx] != 0){
            lazyAddA[lc] += lazyAddA[idx];
            lazyAddB[lc] += lazyAddB[idx];
            lazyAddA[rc] += lazyAddA[idx];
            lazyAddB[rc] += lazyAddB[idx];
            lazyAddA[idx] = lazyAddB[idx] = 0;
        }
    }
    void update(int idx, int l, int r, int ql, int qr, bool setOp, ll A_val, ll B_val) {
        if(ql > r || qr < l) return;
        if(ql <= l && r <= qr){
            if(setOp){
                lazySet[idx] = true;
                lazySetA[idx] = A_val;
                lazySetB[idx] = B_val;
                lazyAddA[idx] = lazyAddB[idx] = 0;
            } else {
                if(lazySet[idx]){
                    lazySetA[idx] += A_val;
                    lazySetB[idx] += B_val;
                } else {
                    lazyAddA[idx] += A_val;
                    lazyAddB[idx] += B_val;
                }
            }
            return;
        }
        pushDown(idx, l, r);
        int m = (l+r)/2;
        update(idx*2, l, m, ql, qr, setOp, A_val, B_val);
        update(idx*2+1, m+1, r, ql, qr, setOp, A_val, B_val);
    }
    ll query(int idx, int l, int r, int pos) {
        if(l == r){
            if(lazySet[idx])
                return lazySetA[idx] + lazySetB[idx]*l;
            return base[l-1] + lazyAddA[idx] + lazyAddB[idx]*l;
        }
        pushDown(idx, l, r);
        int m = (l+r)/2;
        if(pos <= m) return query(idx*2, l, m, pos);
        else return query(idx*2+1, m+1, r, pos);
    }
};

struct Node {
    int l, r;
    int leftVal, rightVal;
    int pre, suf, ans;
    bool allSame;
};

struct SegD {
    int n;
    vector<Node> tree;
    vector<bool> lazySet;
    vector<int> lazySetVal, lazyAdd;
    SegD(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4*n);
        lazySet.assign(4*n, false);
        lazySetVal.assign(4*n, 0);
        lazyAdd.assign(4*n, 0);
        build(1, 1, n, arr);
    }
    Node combine(const Node &L, const Node &R) {
        if(L.ans == 0) return R;
        if(R.ans == 0) return L;
        Node res;
        res.l = L.l; res.r = R.r;
        res.leftVal = L.leftVal; res.rightVal = R.rightVal;
        res.allSame = (L.allSame && R.allSame && (L.rightVal == R.leftVal));
        if(L.allSame && L.leftVal == R.leftVal)
            res.pre = L.ans + R.pre;
        else
            res.pre = L.pre;
        if(R.allSame && R.rightVal == L.rightVal)
            res.suf = R.ans + L.suf;
        else
            res.suf = R.suf;
        res.ans = max({L.ans, R.ans, L.suf + R.pre});
        return res;
    }
    void build(int idx, int l, int r, const vector<int>& arr) {
        tree[idx].l = l; tree[idx].r = r;
        if(l == r) {
            tree[idx].leftVal = tree[idx].rightVal = arr[l-1];
            tree[idx].pre = tree[idx].suf = tree[idx].ans = 1;
            tree[idx].allSame = true;
            return;
        }
        int m = (l+r)/2;
        build(idx*2, l, m, arr);
        build(idx*2+1, m+1, r, arr);
        tree[idx] = combine(tree[idx*2], tree[idx*2+1]);
    }
    void applySet(int idx, int l, int r, int val) {
        tree[idx].leftVal = tree[idx].rightVal = val;
        tree[idx].pre = tree[idx].suf = tree[idx].ans = (r - l + 1);
        tree[idx].allSame = true;
        lazySet[idx] = true;
        lazySetVal[idx] = val;
        lazyAdd[idx] = 0;
    }
    void applyAdd(int idx, int l, int r, int addVal) {
        tree[idx].leftVal += addVal;
        tree[idx].rightVal += addVal;
        if(lazySet[idx])
            lazySetVal[idx] += addVal;
        else
            lazyAdd[idx] += addVal;
    }
    void pushDown(int idx) {
        int l = tree[idx].l, r = tree[idx].r, m = (l+r)/2;
        int lc = idx*2, rc = idx*2+1;
        if(lazySet[idx]) {
            applySet(lc, l, m, lazySetVal[idx]);
            applySet(rc, m+1, r, lazySetVal[idx]);
            lazySet[idx] = false;
            lazySetVal[idx] = 0;
        }
        if(lazyAdd[idx] != 0) {
            applyAdd(lc, l, m, lazyAdd[idx]);
            applyAdd(rc, m+1, r, lazyAdd[idx]);
            lazyAdd[idx] = 0;
        }
    }
    void updateSet(int idx, int ql, int qr, int val) {
        int l = tree[idx].l, r = tree[idx].r;
        if(ql > r || qr < l) return;
        if(ql <= l && r <= qr) {
            applySet(idx, l, r, val);
            return;
        }
        pushDown(idx);
        updateSet(idx*2, ql, qr, val);
        updateSet(idx*2+1, ql, qr, val);
        tree[idx] = combine(tree[idx*2], tree[idx*2+1]);
    }
    void updateAdd(int idx, int ql, int qr, int addVal) {
        int l = tree[idx].l, r = tree[idx].r;
        if(ql > r || qr < l) return;
        if(ql <= l && r <= qr) {
            applyAdd(idx, l, r, addVal);
            return;
        }
        pushDown(idx);
        updateAdd(idx*2, ql, qr, addVal);
        updateAdd(idx*2+1, ql, qr, addVal);
        tree[idx] = combine(tree[idx*2], tree[idx*2+1]);
    }
    Node query(int idx, int ql, int qr) {
        int l = tree[idx].l, r = tree[idx].r;
        if(ql > r || qr < l) return {0,0,0,0,0,true};
        if(ql <= l && r <= qr) return tree[idx];
        pushDown(idx);
        Node L = query(idx*2, ql, qr);
        Node R = query(idx*2+1, ql, qr);
        if(L.ans == 0) return R;
        if(R.ans == 0) return L;
        return combine(L, R);
    }
};

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<ll> A(n);
    for (int i = 0; i < n; i++) cin >> A[i];
    vector<int> D;
    if(n > 1){
        D.resize(n-1);
        for (int i = 0; i < n-1; i++)
            D[i] = A[i+1] - A[i];
    }
    SegA segA(n, A);
    SegD segD(n > 1 ? D : vector<int>());
    while(q--){
        int t;
        cin >> t;
        if(t == 1){
            int L, R; ll S, C;
            cin >> L >> R >> S >> C;
            // Update A with patch: add f(i)=S+(i-L)*C for i in [L,R]
            ll addA = S - C * L, addB = C; 
            segA.update(1, 1, n, L, R, false, addA, addB);
            // Update D:
            if(n > 1){
                if(L > 1){
                    segD.updateAdd(1, L-1, L-1, S);
                }
                if(R < n){
                    segD.updateAdd(1, R, R, - (S + (R - L) * C));
                }
                if(L <= R-1){
                    segD.updateAdd(1, L, R-1, C);
                }
            }
        } else if(t == 2){
            int L, R; ll S, C;
            cin >> L >> R >> S >> C;
            // Rewrite A: set A[i] = S + (i-L)*C for i in [L,R]
            ll setA = S - C * L, setB = C;
            segA.update(1, 1, n, L, R, true, setA, setB);
            if(n > 1){
                if(L > 1){
                    ll prev = segA.query(1, 1, n, L-1);
                    int newD = (int)( (S) - prev );
                    segD.updateSet(1, L-1, L-1, newD);
                }
                if(R < n){
                    ll nxt = segA.query(1, 1, n, R+1);
                    int newD = (int)( nxt - (S + (R - L)*C) );
                    segD.updateSet(1, R, R, newD);
                }
                if(L <= R-1){
                    segD.updateSet(1, L, R-1, (int)C);
                }
            }
        } else {
            int L, R;
            cin >> L >> R;
            if(L == R) cout << 1 << "\n";
            else {
                Node res = segD.query(1, L, R-1);
                cout << res.ans + 1 << "\n";
            }
        }
    }
    return 0;
}

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