Submission #1218388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218388		tapilyoca	Progression (NOI20_progression)	C++20	100 / 100	1233 ms	69924 KiB

Progression

/***********************************************
* auth: tapilyoca                              *
* date: 06/15/2025 at 11:59:22                 *
* dots: https://github.com/tapilyoca/dotilyoca * 
***********************************************/

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define dbg(x) if(1) cerr << #x << ": " << x << endl;

/***********************************************/

struct Data {
    ll l, r, pref, suff, mid;
    ll leftval, rightval;

    Data() : l(0), r(0), pref(0), suff(0), mid(0), leftval(0), rightval(0) {}

    Data(ll left, ll right) {
        l = left, r = right;
        pref = suff = mid = 1;
        leftval = rightval = -1e9; // jusjt set this on creation
    }

    void print() {
        cerr << "DATA FROM " << l << " TO " << r << ", PSM: " << pref << ", " << suff << ", " << mid << endl;
    }
};

const Data ident(-1e9, -1e9);

inline Data mergeData(const Data &a, const Data &b) {
    if(a.l == -1e9) return b;
    if(b.l == -1e9) return a;

    Data out(a.l, b.r);
    
    out.pref = a.pref;
    out.leftval = a.leftval;
    out.suff = b.suff;
    out.rightval = b.rightval;
    out.mid = max(a.mid, b.mid);

    // check: prefix extends to whole?
    if(a.pref == (a.r - a.l + 1) and a.leftval == b.leftval) out.pref = a.pref + b.pref;
    if(b.suff == (b.r - b.l + 1) and b.rightval == a.rightval) out.suff = b.suff + a.suff;
    
    // check: mid overlap?
    if(a.rightval == b.leftval) out.mid = max(out.mid, a.suff + b.pref);

    return out;
}

struct Segtree {
    Segtree *lt, *rt;
    Data val;
    ll lazy_add;
    ll lazy_set;
    ll sum = 0;

    void combine() {
        val = mergeData(lt->val,rt->val);
        sum = lt->sum + rt->sum;
    }

    Segtree(ll left, ll right, vec<int> &a) : val(left,right) {
        if(left > right) {
            val = ident;
            lt = rt = nullptr;
            lazy_add = 0;
            lazy_set = -1e18;
            sum = 0;
            return;
        }

        val.l = left;
        val.r = right;
        lt = rt = nullptr;
        lazy_add = 0;
        lazy_set = -1e18;

        if(val.l == val.r) {
            val.leftval = val.rightval = sum = a[val.l];
            return;
        }
        ll m = (val.l+val.r)>>1;
        lt = new Segtree(val.l,m,a);
        rt = new Segtree(m+1,val.r,a);
        combine();
    }

    void propagate() {
        if(lazy_set != -1e18) {
            val.leftval = val.rightval = lazy_set;
            val.pref = val.suff = val.mid = val.r - val.l + 1;
            sum = (val.r - val.l + 1) * lazy_set;
            if(lt) { 
                lt->lazy_set = rt->lazy_set = lazy_set;
                lt->lazy_add = rt->lazy_add = 0;
            }
            lazy_set = -1e18;
        }

        if(lazy_add != 0) {
            val.leftval += lazy_add;
            val.rightval += lazy_add;
            sum += (val.r - val.l + 1) * lazy_add;
            if(lt) {
                lt->lazy_add += lazy_add;
                rt->lazy_add += lazy_add;
            }
            lazy_add = 0;
        }
    }

    Data query(ll ql, ll qr) {
        propagate();
        if(val.r < ql or qr < val.l) return ident;
        if(ql <= val.l and val.r <= qr) return val;
        return mergeData(lt->query(ql,qr), rt->query(ql,qr));
    }

    ll query_sum(ll ql, ll qr) {
        propagate();
        if(val.r < ql or qr < val.l) return 0ll;
        if(ql <= val.l and val.r <= qr) return sum;
        return lt->query_sum(ql,qr) + rt->query_sum(ql,qr);
    }

    void update_add(ll ul, ll ur, ll add) {
        propagate();
        if(val.r < ul or ur < val.l) return;
        if(ul <= val.l and val.r <= ur) {
            lazy_add += add;
            propagate();
            return;
        }
        lt->update_add(ul,ur,add);
        rt->update_add(ul,ur,add);
        combine();
    }

    void update_set(ll ul, ll ur, ll to_set) {
        propagate();
        if(val.r < ul or ur < val.l) return;
        if(ul <= val.l and val.r <= ur) {
            lazy_set = to_set;
            lazy_add = 0;
            propagate();
            return;
        }
        lt->update_set(ul,ur,to_set);
        rt->update_set(ul,ur,to_set);
        combine();
    }

    void preorder() {
        val.print();
        if(lt) {
            lt->preorder();
            rt->preorder();
        }
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vec<int> a(n,0);
    vec<int> diff(n-1,0);

    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    ll firstElement = a[0];

    for(int i = 1; i < n; i++) {
        diff[i-1] = a[i] - a[i-1];
    }

    // cerr << "DIFF AT START: " << endl;
    // for(auto &x : diff) cerr << x << " ";
    // cerr << endl;

    Segtree st = Segtree(0,n-2,diff);
    
    // st.preorder();

    for(int p = 0; p < q; p++) {
        int type;
        cin >> type;
        if(type == 1) {
            ll l, r, s, c;
            cin >> l >> r >> s >> c;

            if(l == 1) firstElement += s;

            l -= 2;
            r -= 2;
            ll totAdded = (r-l) * c + s;


            // cerr << "Segtree terms: update on " << l << " " << r << endl;
            st.update_add(l,l,s);
            if(l != r) st.update_add(l+1,r,c);
            if(r != n-2) {
                // cerr << "fix diff array, add " << -totAdded << " to " << r+1 << endl;
                st.update_add(r+1,r+1,-totAdded);
            }

            // DEBUG PRINT ARRAY
            // cerr << "DIFF AFTER UPDATE: " << endl;
            // for(int i = 0; i < n-1; i++) cerr << st.query(i,i).leftval << " ";
            // cerr << endl;
        }

        else if(type == 2) {
            ll l, r, s, c;
            cin >> l >> r >> s >> c;

            ll old_first_element = firstElement;
            ll old_prev_element = (l == 1 ? -1e18 : (l == 2 ? old_first_element : old_first_element + st.query_sum(0,l-3)));
            ll old_next_element = (r == n ? -1e18 : old_first_element + st.query_sum(0,r-1));
            ll finalSet = (r-l) * c + s;

            // cerr << "Old first: " << old_first_element << endl;
            // cerr << "old next: " << old_next_element << endl;

            if(l == 1) firstElement = s; // more cases

            l -= 2;
            r -= 2;

            // cerr << "Old previous element: " << old_prev_element << endl;
            st.update_set(l,l,s - old_prev_element);

            if(l != r) st.update_set(l+1,r,c);
            if(r != n-2) { 
                ll soFar = st.query_sum(0,r) + firstElement;
                st.update_set(r+1, r+1, old_next_element - soFar);
            }

        }

        else if(type == 3) {
            // query
            ll l,r;
            cin >> l >> r;
            if(l == r) {
                cout << 1 << endl;
                continue;
            }
            l--;
            r -= 2;

            Data yay = st.query(l,r);
            cout << max({yay.pref,yay.suff,yay.mid}) + 1 << endl;
        }


        // cerr << "END QUERY " << p+1 << " HERE IS ARRAY " << endl;
        // cerr << firstElement << " ";
        // for(int i = 0; i < n-1; i++) {
        //     cerr << st.query_sum(0,i) + firstElement << " ";
        // } cerr << endl;
        // if(p == 0) {
        // for(int i = 0; i < n-1; i++) {
        //     cout << st.query(i,i).leftval << " ";
        // } cout << endl;
        // }

    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;

    while(t--) {
        solve();
    }

    return 0;
}

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