Submission #1218346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218346		tapilyoca	Progression (NOI20_progression)	C++20	0 / 100	557 ms	1114112 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(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(-1e18, -1e18);

Data mergeData(const Data &a, const Data &b) {
    if(a.l == -1e18) return b;
    if(b.l == -1e18) 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 {
    ll l, r;
    Segtree *lt, *rt;
    Data val;

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

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

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

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

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

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-1] = a[i] - a[i-1];
    }

    // for(ll &x : diff) cerr << x << " ";
    // cerr << endl;

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


    while(q--) {
        ll type;
        cin >> type;
        if(type == 1) {
            // patch
            ll l, r, s, c;
            cin >> l >> r >> s >> c;
            assert(0);
        }
        else if(type == 2) {
            // rewrite
            ll l, r, s, c;
            cin >> l >> r >> s >> c;
            assert(0);
        }
        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);
            ll one = yay.pref;
            ll two = yay.suff;
            ll three = yay.mid;
            cout << max({one,two,three}) + 1 << 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