Submission #972699

#	Time	Username	Problem	Language	Result	Execution time	Memory
972699		876pol	Sequence (APIO23_sequence)	C++17	100 / 100	1467 ms	62476 KiB

sequence

#ifndef LOCAL
#pragma GCC optimize("O2")
#pragma GCC target("avx2")
#include "sequence.h"

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define dbg(...)
#define STRUCT_DBG(...)
#else
#include "lib/debug.h"
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = int;
using ld = long double;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
using vll = vector<ll>;
using vpll = vector<pair<ll, ll>>;
using vvll = vector<vector<ll>>;
using vvpll = vector<vector<pair<ll, ll>>>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define RFOR(i, e, s) for (ll i = (ll)e - 1; i >= (ll)s; i--)
#define TRAV(a, c) for (const auto &a : c)
#define all(x) x.begin(), x.end()

const ll MXN = 5e5 + 5;
ll n, suffmx[2 * MXN], suffmn[2 * MXN], prefmx[2 * MXN], prefmn[2 * MXN],
    lsuff[2 * MXN], lprefmx[2 * MXN], lprefmn[2 * MXN];
vec<ll> inds[MXN];

#define lc(x) x + 1
#define rc(x) x + ((tm - tl + 1) << 1ll)

inline void pullsuff(ll v, ll tl, ll tr) {
    if (tl == tr) return;
    ll tm = (tl + tr) >> 1ll;
    suffmx[v] = max(suffmx[lc(v)], suffmx[rc(v)]);
    suffmn[v] = min(suffmn[lc(v)], suffmn[rc(v)]);
}

inline void pullpref(ll v, ll tl, ll tr) {
    if (tl == tr) return;
    ll tm = (tl + tr) >> 1ll;
    prefmx[v] = max(prefmx[lc(v)], prefmx[rc(v)]);
    prefmn[v] = min(prefmn[lc(v)], prefmn[rc(v)]);
}

inline void pushsuff(ll v, ll tl, ll tr) {
    if (!lsuff[v]) return;
    ll tm = (tl + tr) >> 1ll;
    suffmx[v] += lsuff[v];
    suffmn[v] += lsuff[v];
    if (tl != tr) {
        lsuff[lc(v)] += lsuff[v];
        lsuff[rc(v)] += lsuff[v];
    }
    lsuff[v] = 0;
}

inline void pushpref(ll v, ll tl, ll tr) {
    if (!lprefmx[v] && !lprefmn[v]) return;
    ll tm = (tl + tr) >> 1ll;
    prefmx[v] += lprefmx[v];
    prefmn[v] += lprefmn[v];
    if (tl != tr) {
        lprefmx[lc(v)] += lprefmx[v];
        lprefmx[rc(v)] += lprefmx[v];
        lprefmn[lc(v)] += lprefmn[v];
        lprefmn[rc(v)] += lprefmn[v];
    }
    lprefmx[v] = lprefmn[v] = 0;
}

void build(ll v, ll tl, ll tr) {
    if (tl == tr) {
        suffmx[v] = suffmn[v] = n - tl;
        prefmx[v] = prefmn[v] = tl + 1;
    } else {
        ll tm = (tl + tr) >> 1ll;
        build(lc(v), tl, tm);
        build(rc(v), tm + 1, tr);
        pullsuff(v, tl, tr);
        pullpref(v, tl, tr);
    }
}

void update_suff(ll v, ll tl, ll tr, ll r, ll x) {
    ll tm = (tl + tr) >> 1ll;
    pushsuff(v, tl, tr);
    if (r < tl) return;
    if (tr <= r) {
        lsuff[v] += x;
        pushsuff(v, tl, tr);
    } else {
        update_suff(lc(v), tl, tm, r, x);
        if (tm + 1 <= r) {
            update_suff(rc(v), tm + 1, tr, r, x);
        } else {
            pushsuff(rc(v), tm + 1, tr);
        }
        pullsuff(v, tl, tr);
    }
}

void update_prefmx(ll v, ll tl, ll tr, ll l, ll x) {
    ll tm = (tl + tr) >> 1ll;
    pushpref(v, tl, tr);
    if (tr < l) return;
    if (l <= tl) {
        lprefmx[v] += x;
        pushpref(v, tl, tr);
    } else {
        if (tm >= l) {
            update_prefmx(lc(v), tl, tm, l, x);
        } else {
            pushpref(lc(v), tl, tm);
        }
        update_prefmx(rc(v), tm + 1, tr, l, x);
        pullpref(v, tl, tr);
    }
}

void update_prefmn(ll v, ll tl, ll tr, ll l, ll x) {
    ll tm = (tl + tr) >> 1ll;
    pushpref(v, tl, tr);
    if (tr < l) return;
    if (l <= tl) {
        lprefmn[v] += x;
        pushpref(v, tl, tr);
    } else {
        if (tm >= l) {
            update_prefmn(lc(v), tl, tm, l, x);
        } else {
            pushpref(lc(v), tl, tm);
        }
        update_prefmn(rc(v), tm + 1, tr, l, x);
        pullpref(v, tl, tr);
    }
}

inline void one_to_zero(ll ind) {
    update_suff(0, 0, n - 1, ind, -1);
    update_prefmn(0, 0, n - 1, ind, -2);
}

inline void zero_to_negone(ll ind) {
    update_suff(0, 0, n - 1, ind, -1);
    update_prefmx(0, 0, n - 1, ind, -2);
}

const pll query_suff(ll v, ll tl, ll tr, ll r) {
    ll tm = (tl + tr) >> 1ll;
    pushsuff(v, tl, tr);
    if (r < tl) return {INT_MAX, INT_MIN};
    if (tr <= r) {
        return {suffmn[v], suffmx[v]};
    } else {
        pll o1 = query_suff(lc(v), tl, tm, r);
        pll o2 = (tm + 1 <= r) ? query_suff(rc(v), tm + 1, tr, r)
                               : pll{INT_MAX, INT_MIN};
        return {min(o1.first, o2.first), {max(o1.second, o2.second)}};
    }
}

const vll query_point(ll v, ll tl, ll tr, ll ind) {
    ll tm = (tl + tr) >> 1ll;
    pushpref(v, tl, tr);
    pushsuff(v, tl, tr);
    if (tl == tr && tl == ind) {
        return {prefmn[v], prefmx[v], suffmn[v], suffmx[v]};
    } else {
        if (ind <= tm) {
            return query_point(lc(v), tl, tm, ind);
        } else {
            return query_point(rc(v), tm + 1, tr, ind);
        }
    }
};

ll walk_pref(ll v, ll tl, ll tr, ll l, ll r, ll la, ll ra) {
    ll tm = (tl + tr) >> 1ll;
    pushpref(v, tl, tr);
    if (r < tl || tr < l || !(la <= prefmx[v] && prefmn[v] <= ra)) return l;
    if (tl == tr) return tl;
    ll o = walk_pref(rc(v), tm + 1, tr, l, r, la, ra);
    if (o != l) return o;
    return walk_pref(lc(v), tl, tm, l, r, la, ra);
};

int sequence(int _n, vector<int> a) {
    n = _n;
    FOR(i, 0, n) inds[a[i]].push_back(i);
    build(0, 0, n - 1);
    ll ans = 0;
    CFOR(i, 1, n) {
        if (inds[i].empty()) continue;
        TRAV(e, inds[i]) one_to_zero(e);
        TRAV(e, inds[i]) {
            auto o1 = query_suff(0, 0, n - 1, e);
            auto o2 = query_point(0, 0, n - 1, e);
            ll la = -(o1.first - o2[2] - o2[0]) + 1;
            ll ra = -(o1.second - o2[3] - o2[1]) - 1;
            swap(la, ra);
            ll best = walk_pref(0, 0, n - 1, e, n - 1, la, ra);
            auto it1 = upper_bound(all(inds[i]), best);
            auto it2 = lower_bound(all(inds[i]), e);
            ans = max(ans, (ll)(it1 - it2));
        }
        TRAV(e, inds[i]) zero_to_negone(e);
    }
    return ans;
}

// int main() {
//     int N;
//     assert(1 == scanf("%d", &N));

//     std::vector<int> A(N);
//     for (int i = 0; i < N; ++i) {
//         assert(1 == scanf("%d", &A[i]));
//     }

//     int result = sequence(N, A);
//     printf("%d\n", result);
//     return 0;
// }

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 22 / 22
• Subtask 7: 18 / 18