Submission #1182796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182796		Thunnus	Progression (NOI20_progression)	C++20	0 / 100	121 ms	87844 KiB

Progression

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

struct SegTree{
    struct Node{
        int pfv, pfl, sfv, sfl, best, len, lazy, sm;
        bool ad;
        Node(int pfv, int pfl, int sfv, int sfl, int best, int len, int lazy, int sm, bool ad) : pfv(pfv), pfl(pfl), sfv(sfv), sfl(sfl), best(best), len(len), lazy(lazy), sm(sm), ad(ad) {}
        Node() : Node(0, 0, 0, 0, 0, 1, 0, true, 0) {}
    };
    int n;
    vector<Node> st;
    SegTree(int n) : n(n), st(4 * n) {}

    inline Node combine(Node a, Node b){
        Node c;
        c.len = a.len + b.len;
        c.sm = a.sm + b.sm;
        c.pfl = a.pfl, c.pfv = a.pfv;
        c.sfl = b.sfl, c.sfv = b.sfv;
        if(a.pfl == a.len && a.pfv == b.pfv){
            c.pfl = a.pfl + b.pfl;
        }
        if(b.sfl == b.len && a.sfv == b.sfv){
            c.sfl = b.sfl + a.sfl;
        }
        c.best = max(a.best, b.best); // the best mustn't be a prefix or a suffix of the current contained region (because we built our segment tree over an difference array)
        if(a.sfl != a.len){
            c.best = max(c.best, a.sfl);
        }
        if(b.pfl != b.len){
            c.best = max(b.pfl, c.best);
        }
        if(a.sfv == b.pfv && a.sfl != a.len && b.pfl != b.len){
            c.best = max(c.best, a.sfl + b.pfl);
        }
        return c;
    }

    inline void apply(int v, int val, bool adding){
        if(adding){
            st[v].pfv += val;
            st[v].sfv += val;
            st[v].sm += st[v].len * val;
            st[v].lazy += val;
            st[v].ad = true;
        }
        else{
            st[v].pfv = val;
            st[v].sfv = val;
            st[v].lazy = val;
            st[v].sm = st[v].len * val;
            st[v].ad = false;
        }
        return;
    }

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

    inline void add(int al, int ar, int val, int v, int tl, int tr){
        if(al > tr || tl > ar) return;
        if(al >= tl && ar <= tr){
            apply(v, val, true);
            return;
        }
        int mid = (tl + tr) / 2;
        propagate(v);
        add(al, ar, 2 * v, val, tl, mid);
        add(al, ar, 2 * v + 1, val, mid + 1, tr);
        st[v] = combine(st[2 * v], st[2 * v + 1]);
        return;
    }

    inline void add(int al, int ar, int val){
        add(al, ar, val, 1, 1, n);
        return;
    }

    inline void update(int ul, int ur, int val, int v, int tl, int tr){
        if(ul > tr || tl > ur) return;
        if(ul >= tl && ur <= tr){
            apply(v, val, false);
            return;
        }
        int mid = (tl + tr) / 2;
        propagate(v);
        update(ul, ur, val, 2 * v, tl, mid);
        update(ul, ur, val, 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 val){
        update(ul, ur, val, 1, 1, n);
        return;
    }

    inline Node query(int ql, int qr, int v, int tl, int tr){
        if(ql > tr || tl > qr) return Node();
        if(ql >= tl && qr <= tr) 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_best(int ql, int qr){
        return query(ql, qr, 1, 1, n).best;
    }

    inline int query_sum(int ql, int qr){
        if(qr <= 1) return 0; 
        return query(ql, qr - 1, 1, 1, n).sm;
    }
};

inline void solve(){
    int n, q;
    cin >> n >> q;
    vi a(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    SegTree st(n);
    for(int i = 1; i <= n; i++){
        st.update(i, i, a[i] - a[i - 1]);
    }
    while(q--){
        int type, l, r, s, c;
        cin >> type >> l >> r;
        if(type == 1){
            cin >> s >> c;
            st.add(l, l, s);
            if(l != r){
                st.add(l + 1, r, c);
            }
            if(r < n){
                st.add(r + 1, r + 1, -(s + (r - l) * c));
            }
        }
        else if(type == 2){
            cin >> s >> c;
            int sm = st.query_sum(1, l), before = st.query_sum(l, r + 1);
            st.update(l, l, s - sm);
            if(l != r){
                st.update(l + 1, r, c);
            }
            int after = st.query_sum(l, r + 1);
            if(r < n){
                st.update(r + 1, r + 1, before - after);
            }
        }
        else{
            cout << st.query_best(l, r) + 1 << "\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