oj.uz

Submission #972699

# Submission time Handle Problem Language Result Execution time Memory
972699 2024-05-01T02:32:39 Z 876pol Sequence (APIO23_sequence) C++17
100 / 100
 1467 ms 62476 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21084 KB Output is correct
2 Correct 7 ms 21084 KB Output is correct
3 Correct 5 ms 21332 KB Output is correct
4 Correct 6 ms 21336 KB Output is correct
5 Correct 5 ms 21080 KB Output is correct
6 Correct 5 ms 21340 KB Output is correct
7 Correct 5 ms 21080 KB Output is correct
8 Correct 5 ms 21084 KB Output is correct
9 Correct 5 ms 21116 KB Output is correct
10 Correct 5 ms 21084 KB Output is correct
11 Correct 5 ms 21080 KB Output is correct
12 Correct 5 ms 21084 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21084 KB Output is correct
2 Correct 7 ms 21084 KB Output is correct
3 Correct 5 ms 21332 KB Output is correct
4 Correct 6 ms 21336 KB Output is correct
5 Correct 5 ms 21080 KB Output is correct
6 Correct 5 ms 21340 KB Output is correct
7 Correct 5 ms 21080 KB Output is correct
8 Correct 5 ms 21084 KB Output is correct
9 Correct 5 ms 21116 KB Output is correct
10 Correct 5 ms 21084 KB Output is correct
11 Correct 5 ms 21080 KB Output is correct
12 Correct 5 ms 21084 KB Output is correct
13 Correct 7 ms 21080 KB Output is correct
14 Correct 7 ms 21084 KB Output is correct
15 Correct 7 ms 21084 KB Output is correct
16 Correct 7 ms 21084 KB Output is correct
17 Correct 6 ms 21084 KB Output is correct
18 Correct 6 ms 21084 KB Output is correct
19 Correct 7 ms 21196 KB Output is correct
20 Correct 7 ms 21124 KB Output is correct
21 Correct 7 ms 21084 KB Output is correct
22 Correct 8 ms 21084 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21084 KB Output is correct
2 Correct 684 ms 56568 KB Output is correct
3 Correct 690 ms 56532 KB Output is correct
4 Correct 626 ms 46772 KB Output is correct
5 Correct 671 ms 55728 KB Output is correct
6 Correct 655 ms 55600 KB Output is correct
7 Correct 619 ms 47192 KB Output is correct
8 Correct 606 ms 47400 KB Output is correct
9 Correct 608 ms 46640 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 21084 KB Output is correct
2 Correct 640 ms 46692 KB Output is correct
3 Correct 725 ms 46564 KB Output is correct
4 Correct 646 ms 46520 KB Output is correct
5 Correct 662 ms 46580 KB Output is correct
6 Correct 616 ms 46640 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 62332 KB Output is correct
2 Correct 954 ms 62476 KB Output is correct
3 Correct 1006 ms 61852 KB Output is correct
4 Correct 933 ms 61780 KB Output is correct
5 Correct 880 ms 58432 KB Output is correct
6 Correct 836 ms 58432 KB Output is correct
7 Correct 702 ms 57168 KB Output is correct
8 Correct 685 ms 56912 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21084 KB Output is correct
2 Correct 7 ms 21084 KB Output is correct
3 Correct 5 ms 21332 KB Output is correct
4 Correct 6 ms 21336 KB Output is correct
5 Correct 5 ms 21080 KB Output is correct
6 Correct 5 ms 21340 KB Output is correct
7 Correct 5 ms 21080 KB Output is correct
8 Correct 5 ms 21084 KB Output is correct
9 Correct 5 ms 21116 KB Output is correct
10 Correct 5 ms 21084 KB Output is correct
11 Correct 5 ms 21080 KB Output is correct
12 Correct 5 ms 21084 KB Output is correct
13 Correct 7 ms 21080 KB Output is correct
14 Correct 7 ms 21084 KB Output is correct
15 Correct 7 ms 21084 KB Output is correct
16 Correct 7 ms 21084 KB Output is correct
17 Correct 6 ms 21084 KB Output is correct
18 Correct 6 ms 21084 KB Output is correct
19 Correct 7 ms 21196 KB Output is correct
20 Correct 7 ms 21124 KB Output is correct
21 Correct 7 ms 21084 KB Output is correct
22 Correct 8 ms 21084 KB Output is correct
23 Correct 133 ms 24920 KB Output is correct
24 Correct 135 ms 24920 KB Output is correct
25 Correct 134 ms 24924 KB Output is correct
26 Correct 143 ms 23868 KB Output is correct
27 Correct 127 ms 23896 KB Output is correct
28 Correct 126 ms 23976 KB Output is correct
29 Correct 110 ms 23384 KB Output is correct
30 Correct 97 ms 23640 KB Output is correct
31 Correct 87 ms 23752 KB Output is correct
32 Correct 91 ms 25936 KB Output is correct
33 Correct 158 ms 24668 KB Output is correct
34 Correct 132 ms 24712 KB Output is correct
35 Correct 135 ms 24600 KB Output is correct
36 Correct 130 ms 24656 KB Output is correct
37 Correct 136 ms 25012 KB Output is correct
38 Correct 126 ms 24904 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21084 KB Output is correct
2 Correct 7 ms 21084 KB Output is correct
3 Correct 5 ms 21332 KB Output is correct
4 Correct 6 ms 21336 KB Output is correct
5 Correct 5 ms 21080 KB Output is correct
6 Correct 5 ms 21340 KB Output is correct
7 Correct 5 ms 21080 KB Output is correct
8 Correct 5 ms 21084 KB Output is correct
9 Correct 5 ms 21116 KB Output is correct
10 Correct 5 ms 21084 KB Output is correct
11 Correct 5 ms 21080 KB Output is correct
12 Correct 5 ms 21084 KB Output is correct
13 Correct 7 ms 21080 KB Output is correct
14 Correct 7 ms 21084 KB Output is correct
15 Correct 7 ms 21084 KB Output is correct
16 Correct 7 ms 21084 KB Output is correct
17 Correct 6 ms 21084 KB Output is correct
18 Correct 6 ms 21084 KB Output is correct
19 Correct 7 ms 21196 KB Output is correct
20 Correct 7 ms 21124 KB Output is correct
21 Correct 7 ms 21084 KB Output is correct
22 Correct 8 ms 21084 KB Output is correct
23 Correct 684 ms 56568 KB Output is correct
24 Correct 690 ms 56532 KB Output is correct
25 Correct 626 ms 46772 KB Output is correct
26 Correct 671 ms 55728 KB Output is correct
27 Correct 655 ms 55600 KB Output is correct
28 Correct 619 ms 47192 KB Output is correct
29 Correct 606 ms 47400 KB Output is correct
30 Correct 608 ms 46640 KB Output is correct
31 Correct 640 ms 46692 KB Output is correct
32 Correct 725 ms 46564 KB Output is correct
33 Correct 646 ms 46520 KB Output is correct
34 Correct 662 ms 46580 KB Output is correct
35 Correct 616 ms 46640 KB Output is correct
36 Correct 970 ms 62332 KB Output is correct
37 Correct 954 ms 62476 KB Output is correct
38 Correct 1006 ms 61852 KB Output is correct
39 Correct 933 ms 61780 KB Output is correct
40 Correct 880 ms 58432 KB Output is correct
41 Correct 836 ms 58432 KB Output is correct
42 Correct 702 ms 57168 KB Output is correct
43 Correct 685 ms 56912 KB Output is correct
44 Correct 133 ms 24920 KB Output is correct
45 Correct 135 ms 24920 KB Output is correct
46 Correct 134 ms 24924 KB Output is correct
47 Correct 143 ms 23868 KB Output is correct
48 Correct 127 ms 23896 KB Output is correct
49 Correct 126 ms 23976 KB Output is correct
50 Correct 110 ms 23384 KB Output is correct
51 Correct 97 ms 23640 KB Output is correct
52 Correct 87 ms 23752 KB Output is correct
53 Correct 91 ms 25936 KB Output is correct
54 Correct 158 ms 24668 KB Output is correct
55 Correct 132 ms 24712 KB Output is correct
56 Correct 135 ms 24600 KB Output is correct
57 Correct 130 ms 24656 KB Output is correct
58 Correct 136 ms 25012 KB Output is correct
59 Correct 126 ms 24904 KB Output is correct
60 Correct 1389 ms 56728 KB Output is correct
61 Correct 1380 ms 56660 KB Output is correct
62 Correct 1467 ms 56916 KB Output is correct
63 Correct 1313 ms 48572 KB Output is correct
64 Correct 1288 ms 48560 KB Output is correct
65 Correct 1283 ms 48544 KB Output is correct
66 Correct 742 ms 46700 KB Output is correct
67 Correct 718 ms 46688 KB Output is correct
68 Correct 630 ms 48836 KB Output is correct
69 Correct 611 ms 62288 KB Output is correct
70 Correct 1403 ms 55836 KB Output is correct
71 Correct 1358 ms 56016 KB Output is correct
72 Correct 1252 ms 55144 KB Output is correct
73 Correct 1287 ms 55484 KB Output is correct
74 Correct 1335 ms 55304 KB Output is correct
75 Correct 1307 ms 55652 KB Output is correct