Submission #1218321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218321		tapilyoca	Progression (NOI20_progression)	C++20	0 / 100	764 ms	64196 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 Segtree {
    ll l, r;
    Segtree *lt, *rt;
    ll prefLength, prefVal;
    ll suffLength, suffVal;
    ll midLength, midVal;

    void combine() {
        if(lt->prefLength == lt->r - lt->l + 1 and rt->prefVal == lt->prefVal) {
            prefLength = lt->prefLength + rt->prefLength;
            prefVal = lt->prefVal;
        } else {
            prefLength = lt->prefLength;
            prefVal = lt->prefVal;
        }

        if(rt->suffLength == rt->r - rt->l + 1 and lt->suffVal == rt->suffVal) {
            suffLength = rt->suffLength + lt->suffLength;
            suffVal = rt->suffVal;
        } else {
            suffLength = rt->suffLength;
            suffVal = rt->suffVal;
        }

        midLength = max(lt->midLength, rt->midLength);
        midVal = (lt->midLength > rt->midLength ? lt->midVal : rt->midVal);
        
        // unlike maxsubarray sum consider case where you dont add suff/pref
        if(lt->suffLength > midLength) {
            midLength = lt->suffLength;
            midVal = lt->suffVal;
        }
        
        if(rt -> prefLength > midLength) {
            midLength = rt->prefLength;
            midVal = rt->prefVal;
        }

        // both eqqual
        if(lt->suffVal == rt->prefVal) {
            if(lt->suffLength + rt->prefLength > midLength) {
                midLength = lt->suffLength + rt->prefLength;
                midVal = lt->suffVal;
            }
        }
    }

    Segtree(ll left, ll right, vll &a) {
        l = left;
        r = right;
        lt = rt = nullptr;

        if(l == r) {
            prefLength = suffLength = midLength = 1;
            prefVal = suffVal = midVal = a[l];
            return;
        }
        ll m = (l+r)>>1;
        lt = new Segtree(l,m,a);
        rt = new Segtree(m+1,r,a);
        combine();
    }

    ll query(ll ql, ll qr) {
        if(r < ql or qr < l) return -1;
        if(ql <= l and r <= qr) {
            ll one = prefLength;
            ll two = min(r-l+1,midLength+1);
            ll three = min(r-l+1,suffLength+1);
            return max({one,two,three});
        }

        // jesus christ
        ll one = lt->query(ql,qr);
        ll two = rt->query(ql,qr);
        // check middle
        ll mid = 0;
        if(ql <= lt->r and rt->l <= qr and lt->suffVal == rt->prefVal) {
            ll takeLeft = min(lt->suffLength, lt->r - max(ql,lt->l) + 1);
            ll takeRight = min(rt->prefLength, min(qr, rt->r) - rt-> l + 1);
            mid = takeLeft + takeRight;
        }
        return max({one,two,mid});
    }
};

void solve() {
    ll n, q;
    cin >> n >> q;
    vll a(n,0);
    vll diff(n+1,0);

    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // diff[0] = a[0];
    cerr << diff[0] << " ";
    for(int i = 1; i < n; i++) {
        diff[i] = a[i] - a[i-1];
        cerr << diff[i] << " ";
    } cerr << endl;

    Segtree st = Segtree(0,n-1,diff);

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

            cout << min(r-l+1,st.query(l,r)) << endl;
        }
    }
}

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

    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