제출 #1298761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1298761		Thunnus	Progression (NOI20_progression)	C++20	0 / 100	615 ms	1114112 KiB

Progression

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,O3")
using namespace std;
using i64 = long long;
//#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define se second
#define fi first
#define pii pair<int, int>
#define sz(x) (int)(x).size()

struct ASegTree{
    struct Node{
        i64 sum;
        int mult;
        i64 lazysum = 0, lazymult = 0;
        bool set0 = false;
        Node(i64 sm, int mul, i64 lzs, i64 lzm, bool b) : sum(sm), mult(mul), lazysum(lzs), lazymult(lzm), set0(b) {}
        Node() : Node(0, 0, 0, 0, false) {}  
    };
    int n;
    vector<Node> st;
    ASegTree(int n) : n(n), st(4 * n) {}

    inline void apply(int v, int sm, int ml, bool set0){
        if(set0){
            st[v].sum = 0;
            st[v].lazysum = 0;
            st[v].lazymult = 0;
            st[v].set0 = true;
            return;
        }
        st[v].sum += sm;
        st[v].lazysum += sm;
        st[v].sum += st[v].mult * ml;
        st[v].lazymult += ml;
        return;
    }

    inline void propagate(int v){
        if(st[v].set0){
            apply(2 * v, 0, 0, true);
            apply(2 * v + 1, 0, 0, true);
        }
        apply(2 * v, st[v].lazysum, st[v].lazymult, false);
        apply(2 * v + 1, st[v].lazysum, st[v].lazymult, false);
        st[v].lazysum = st[v].lazymult = 0;
        st[v].set0 = false;
        return;
    }

    inline void build(int v, int tl, int tr, const vi &a){
        if(tl == tr){
            st[v] = {a[tl - 1], tl - 1, 0, 0, false};
            return;
        }
        int mid = (tl + tr) / 2;
        build(2 * v, tl, mid, a);
        build(2 * v + 1, mid + 1, tr, a);
        st[v].sum = st[2 * v].sum + st[2 * v + 1].sum;
        return;
    }

    inline void build(const vi &a){
        build(1, 1, n, a);
    }

    inline void update(int ul, int ur, int sm, int ml, bool set0, int v, int tl, int tr){
        if(ul > tr || tl > ur) return;
        if(ul <= tl && tr <= ur){
            apply(v, sm, ml, set0);
            return;
        }
        int mid = (tl + tr) / 2;
        propagate(v);
        update(ul, ur, sm, ml, set0, 2 * v, tl, mid);
        update(ul, ur, sm, ml, set0, 2 * v + 1, mid + 1, tr);
        st[v].sum = st[2 * v].sum + st[2 * v + 1].sum;
        return;
    }

    inline void update(int ul, int ur, int sm, int ml, bool set0){
        update(ul + 1, ur + 1, sm, ml, set0, 1, 1, n);
    }

    inline i64 query(int pos, int v, int tl, int tr){
        if(tl == tr){
            return st[v].sum;
        }
        int mid = (tl + tr) / 2;
        propagate(v);
        if(pos <= mid){
            return query(pos, 2 * v, tl, mid);
        }
        else{
            return query(pos, 2 * v + 1, mid + 1, tr);
        }
    }

    inline i64 query(int pos){
        return query(pos + 1, 1, 1, n);
    }
};

struct DSegTree{
    struct Node{
        i64 pval, sval;
        int pf, sf, sub;
        i64 lazyadd = 0;
        int len;
        bool set0 = false;
        Node(i64 pv, i64 sv, int pf, int sf, int sub, i64 lza, int len, bool set0) : pval(pv), sval(sv), pf(pf), sf(sf), sub(sub), lazyadd(lza), len(len), set0(set0) {}
        Node() : Node(0, 0, 0, 0, 0, 0, 0, false) {}
    };
    int n;
    vector<Node> st;
    DSegTree(int n) : n(n), st(4 * n) {}

    inline Node combine(const Node &a, const Node &b){
        Node c;
        c.len = a.len + b.len;
        c.pval = a.pval,
        c.sval = b.sval;
        c.pf = a.pf;
        if(a.len == a.pf && a.sval == b.pval){
            c.pf = a.len + b.pf;
        }
        c.sf = b.sf;
        if(b.len == b.sf && a.sval == b.pval){
            c.sf = b.len + a.sf;
        }
        c.sub = max({c.sf, c.pf, a.sub, b.sub});
        if(a.sval == b.pval){
            c.sub = max(c.sub, a.sf + b.pf);
        }
        return c;
    }

    inline void apply(int v, int addval, bool set0){
        if(set0){
            st[v].pval = st[v].sval = st[v].lazyadd = 0;
            st[v].pf = st[v].sf = st[v].sub = st[v].len;
            st[v].set0 = true;
            return;
        }
        st[v].pval += addval, st[v].sval += addval, st[v].lazyadd += addval;
        return;
    }

    inline void propagate(int v){
        if(st[v].set0){
            apply(2 * v, 0, true);
            apply(2 * v + 1, 0, true);
        }
        apply(2 * v, st[v].lazyadd, false);
        apply(2 * v + 1, st[v].lazyadd, false);
        st[v].lazyadd = 0;
        st[v].set0 = false;
        return;
    } 

    inline void build(int v, int tl, int tr, const vi &a){
        if(tl == tr){
            st[v] = {a[tl - 1], a[tl - 1], 1, 1, 1, 0, 1, false};
            return;
        }
        int mid = (tl + tr) / 2;
        build(2 * v, tl, mid, a);
        build(2 * v + 1, mid + 1, tr, a);
        st[v] = combine(st[2 * v], st[2 * v + 1]);
        return;
    }

    inline void build(const vi &a){
        build(1, 1, n, a);
    }

    inline void update(int ul, int ur, int add, bool set0, int v, int tl, int tr){
        if(ul > tr || tl > ur) return;
        if(ul <= tl && tr <= ur){
            apply(v, add, set0);
            return;
        }
        int mid = (tl + tr) / 2;
        propagate(v);
        update(ul, ur, add, set0, 2 * v, tl, mid);
        update(ul, ur, add, set0, 2 * v + 1, mid + 1, tr);
        st[v] = combine(st[2 * v], st[2 * v + 1]);
        return;
    }

    inline void update(int ul, int ur, int add, bool set0){
        update(ul + 1, ur + 1, add, set0, 1, 1, n);
    }

    inline Node query(int ql, int qr, int v, int tl, int tr){
        if(ql > tr || tl > qr) return Node();
        if(ql <= tl && tr <= qr) return st[v];
        int mid = (tl + tr) / 2;
        propagate(v);
        return combine(query(ql, qr, 2 * v, tl, mid), query(ql, qr, 2 * v + 1, mid + 1, tr));
    }

    inline int query(int ql, int qr){
        return query(ql + 1, qr + 1, 1, 1, n).sub;
    }
};

inline void solve(){
    int n, q;
    cin >> n >> q;
    vi a(n), d(n - 1);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(i){
            d[i - 1] = a[i] - a[i - 1];
        }
    }
    ASegTree aseg(n);
    aseg.build(a);
    DSegTree dseg(n - 1);
    dseg.build(d);

    auto patch = [&](int l, int r, int s, int c) -> void {
        aseg.update(l, r, s - l * c, c, false);
        if(l){
            dseg.update(l - 1, l - 1, s, false);
        }
        if(l < r){
            dseg.update(l, r - 1, c, false);
        }
        if(r + 1 < n){
            dseg.update(r, r, -s - (r - l) * c, false);
        }
        return;
    };

    auto rewrite = [&](int l, int r, int s, int c) -> void {
        aseg.update(l, r, 0, 0, true);
        aseg.update(l, r, s - l * c, c, false);
        if(l){
            i64 befa = aseg.query(l - 1);
            dseg.update(l - 1, l - 1, 0, true);
            dseg.update(l - 1, l - 1, s - befa, false);
        }
        if(l < r){
            dseg.update(l, r - 1, 0, true);
            dseg.update(l, r - 1, c, false);
        }
        if(r + 1 < n){
            i64 afa = aseg.query(r + 1);
            dseg.update(r, r, 0, true);
            dseg.update(r, r, s + (r - l) * c - afa, false);
        }
        return;
    };

    auto evaluate = [&](int l, int r) -> int {
        int ans = 0;
        if(l < r){
            ans = max(ans, dseg.query(l, r - 1));
            //cout << "l: " << l << " r: " << r << " dseg: " << dseg.query(l, r - 1) << "\n";
        }
        return ans + 1;
    };

    while(q--){
        int type, l, r;
        cin >> type >> l >> r;
        l--, r--;
        if(type == 1){
			int s, c;
            cin >> s >> c;
            patch(l, r, s, c);
        }
        else if(type == 2){
			int s, c;
            cin >> s >> c;
            rewrite(l, r, s, c);
        }
        else{
            cout << evaluate(l, r) << "\n";
        }
    }
    return;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    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