Submission #689681

#	Time	Username	Problem	Language	Result	Execution time	Memory
689681		saayan007	Progression (NOI20_progression)	C++17	0 / 100	275 ms	55256 KiB

Progression

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

using ll = long long;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using vi = vector<int>;
using vl = vector<long long>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;

#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first 
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const ll mxn = 3e5L + 1;
ll n, q;
ll d[mxn];
ll a[mxn];

struct item {
    ll zer, one, zlt, zrt, olt, ort;    

    item() {
        zer = one = zlt = zrt = olt = ort = 0; 
    }
};

struct SegTree {
    ll n;
    item id;
    vector<item> tree;

    SegTree(ll N) {
        init(N, id);
    }

    void init(ll N, item x) {
        id = x;
        n = N;
        while(__builtin_popcountll(n) != 1) ++n;

        tree.resize(2*n, id);
    }

    void build() {
        build(1, 0, n - 1);
    }

    void build(ll x, ll lx, ll rx) {
        if(lx == rx)
            return;
        ll d = (lx + rx) / 2;
        build(2*x, lx, d);
        build(2*x + 1, d + 1, rx);
        tree[x] = merge(tree[2*x], tree[2*x + 1], (rx - lx + 1) / 2);
    }

    item query(ll x, ll lx, ll rx, ll l, ll r) {
        if(lx > r || rx < l)
            return id;
        if(lx >= l && rx <= r)
            return tree[x];

        ll d = (lx + rx) / 2;
        item a = query(2*x, lx, d, l, r);
        item b = query(2*x + 1, d + 1, rx, l, r);

        return merge(a, b, (rx - lx + 1) / 2);
    }

    ll query(ll ql, ll qh) {
        item res = query(1, 0, n - 1, ql, qh);
        return max(res.one, res.zer);
    }

    item merge(item lhs, item rhs, ll sz) {
        item ans;
        // ones
        ans.olt = lhs.olt;
        if(lhs.olt == sz)
            ans.olt += rhs.olt;

        ans.ort = rhs.ort;
        if(rhs.ort == sz) {
            ans.ort += lhs.ort;
        }

        ans.one = max({lhs.one, rhs.one, lhs.ort + rhs.olt});

        // zeroes
        ans.zlt = lhs.zlt;
        if(lhs.zlt == sz) {
            ans.zlt += rhs.zlt;
        }

        ans.zrt = rhs.zrt;
        if(rhs.zrt == sz) {
            ans.zrt += lhs.zrt;
        }

        ans.zer = max({lhs.zer, rhs.zer, lhs.zrt + rhs.zlt});
        return ans;
    }
};


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

    cin >> n >> q;
    fur(i, 1, n) {
        cin >> d[i];
    }

    ruf(i, n, 2) {
        d[i] = d[i] - d[i - 1];
    }
    d[1] = d[2];
    // fur(i, 1, n) {
        // cout << d[i] << ' ';
    // }
    // cout << nl;

    ll cur = 1;
    fur(i, 1, n) {
        ll j = i;
        a[j] = cur;
        while(j + 1 <= n && d[j + 1] == d[i]) {
            ++j;
            a[j] = cur;
        }
        cur = 1 - cur;
        i = j;
    }

    // fur(i, 1, n) {
        // cout << a[i] << ' ';
    // }
    // cout << nl;

    SegTree st(n);
    fur(i, 1, n) {
        if(a[i] == 0) {
            st.tree[i - 1 + st.n].zer = 1;
            st.tree[i - 1 + st.n].zrt = 1;
            st.tree[i - 1 + st.n].zlt = 1;
        } else {
            st.tree[i - 1 + st.n].one = 1;
            st.tree[i - 1 + st.n].ort = 1;
            st.tree[i - 1 + st.n].olt = 1;
        }
    }
    st.build();

    while(q--) {
        ll t;
        cin >> t;
        if(t == 1) {
            ll l, r, s, c;
            cin >> l >> r >> s >> c;
        }
        else if(t == 2) {
            ll l, r, s, c;
            cin >> l >> r >> s >> c;
        }
        else if(t == 3) {
            ll l, r;
            cin >> l >> r;
            ll res = st.query(l - 1, r - 1);
            if(res != r - l + 1)
                ++res;
            cout << res << nl;
        }
    }
}

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