Submission #690882

#	Time	Username	Problem	Language	Result	Execution time	Memory
690882		true22	Progression (NOI20_progression)	C++14	0 / 100	337 ms	63896 KiB

Progression

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

typedef pair<ll, ll> pl;
typedef vector<ll> vl;   
typedef vector<pl> vp;

#define nl "\n"
#define fr first
#define sc second
#define pb push_back

#define all(x) x.begin(), x.end()
#define fur(i, a, b) for(ll i = a; i <= b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= b; --i)
#define pv(x) for(auto k : x){cout << k << " ";} cout << nl

const ll inf = 1e17;

struct node{

    ll suffix, prefix, sufval, preval, sublen, subval, lenseg;

    node(ll x){
        suffix = prefix = sublen = lenseg = 1;
        sufval = preval = subval = x;
    }

    node(){
        suffix = prefix = sublen = lenseg = 0;
        sufval = preval = subval = inf;
    }
    
    void print(){
        cout << "suffix: " << suffix << ' ' << sufval << nl;
        cout << "prefix: " << prefix << ' ' << preval << nl;
        cout << "subarr: " << sublen << ' ' << subval << nl;
        cout << "lenseg = " << lenseg << nl;
    }

};

ll n, sz;
vl b, d;
vector<node> st;

/*
    Subtask:
    There are no patch and rewrite operations
    - Now, if we build a difference array on the given d
        then we have to query the length of the longest
        constant subarray
*/



node merge(node a, node b){
    node res;
    res.lenseg = a.lenseg + b.lenseg;

    // if (a.lenseg == 0)
    //     return b;
    // if (b.lenseg == 0)
    //     return a;
    // prefix:
    // take the left, and check if you can take the right
    res.prefix = a.prefix;
    res.preval = a.preval;
    if (a.prefix == a.lenseg && a.sufval == b.preval)
        res.prefix += b.prefix;
    

    // suffix
    // take the right, and check if you can go left
    res.suffix = b.suffix;
    res.sufval = b.sufval;
    if (b.suffix == b.lenseg && a.sufval == b.preval)
        res.suffix += a.suffix;
    

    // subarray
    // either in a or b, or both, or the suffix or(and) prefix
    res.sublen = -1;
    if (a.prefix > res.sublen){
        res.sublen = a.prefix;
        res.subval = a.preval;
    }
    if (b.suffix > res.sublen){
        res.sublen = b.suffix;
        res.subval = b.sufval;
    }
    if (a.sublen > res.sublen){
        res.sublen = a.sublen;
        res.subval = a.subval;
    }

    if (b.sublen > res.sublen){
        res.sublen = b.sublen;
        res.subval = b.subval;
    }

    if (a.sufval == b.preval){
        if (a.suffix + b.prefix > res.sublen){
            res.sublen = a.suffix + b.prefix;
            res.subval = a.sufval;
        }
    }

    return res;
}


node seg(ll l, ll r, ll k, ll kl, ll kr){
    if (kl > r || kr < l)
        return node();

    if (kl >= l && kr <= r)
        return st[k];
    
    ll m = (kl + kr)/2;
    node c = merge(seg(l, r, 2 *k, kl, m), seg(l, r, 2*k + 1, m + 1, kr));
    return c;
}



void solve(){
   ll t;
   cin >> t;
   // t = 3;
   ll l, r;
   cin >> l >> r;
   
   node nd = seg(l, r, 1, 1, sz);
   ll res = max(nd.prefix, max(nd.suffix + 1, nd.sublen + 1));
   res = min(res, r - l + 1);
   cout << res<< nl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll q;
    cin >> n >> q;

    b.resize(n + 1, 0);
    d.resize(n + 1, 0);

    fur(i, 1, n)
        cin >> b[i];
    // fur(i, 1, n)
    //     cout << i << ' ';
    // cout << nl;
    
    fur(i, 1, n)
        d[i] = b[i] - b[i - 1];
    
    //cout << nl;

    

    sz = n;
    while(__builtin_popcountll(sz) != 1){
        sz++;
    }
    st.resize(2*sz, node());
    fur(i, 0, n - 1)
        st[i + sz] = node(d[i + 1]);
    ruf(i, sz - 1, 1)
        st[i] = merge(st[2 * i], st[2*i + 1]);

    //st[1].print();

    while(q--){
        
        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