Submission #1270260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270260		dizzy_groovy	Sequence (APIO23_sequence)	C++20	69 / 100	421 ms	111076 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

struct mnmx{
    long long mn, mx;
    mnmx() {}
    mnmx(long long mn, long long mx) : mn(mn), mx(mx) {}
};

mnmx operator+(mnmx a, mnmx b) {
    return mnmx(min(a.mn, b.mn), max(a.mx, b.mx));
}

struct Segment_tree{
    struct Node{
        long long l, r;
        long long su = 0;
        long long mn;
        long long mx;
        Node() {}
        Node(long long ind, long long x) : l(ind), r(ind + 1), mn(min(0ll, x)), mx(max(0ll, x)), su(x) {}
        Node(Node l, Node r) : l(l.l), r(r.r), su(l.su + r.su), mx(max(l.mx, l.su + r.mx)), mn(min(l.mn, l.su + r.mn)) {}
    };
    vector<Node> tr;
    void build(long long i, long long l, long long r, long long fill) {
        if (r - l == 1) {
            tr[i] = Node(l, fill);
            return;
        }
        long long m = (l + r) / 2;
        build(2 * i + 1, l, m, fill);
        build(2 * i + 2, m, r, fill);
        tr[i] = Node(tr[2 * i + 1], tr[2 * i + 2]);
    }
    void upd(long long ind, long long x, long long i = 0) {
        if (ind < tr[i].l || ind >= tr[i].r) return;
        if (tr[i].r - tr[i].l == 1) {
            tr[i] = Node(ind, x);
            return;
        }
        upd(ind, x, 2 * i + 1);
        upd(ind, x, 2 * i + 2);
        tr[i] = Node(tr[2 * i + 1], tr[2 * i + 2]);
    }
    Node get(long long l, long long r, long long i = 0) {
        if (l >= r) return Node(l, 0);
        if (l <= tr[i].l && tr[i].r <= r) {
            return tr[i];
        }
        if ((tr[i].l + tr[i].r) / 2 <= l) return get(l, r, 2 * i + 2);
        if ((tr[i].l + tr[i].r) / 2 >= r) return get(l, r, 2 * i + 1);
        return Node(get(l, r, 2 * i + 1), get(l, r, 2 * i + 2));
    }
    Node get2(long long l, long long r) {
        auto ans1 = get(l, r);
        auto ans2 = get(0, l);
        ans1.mn += ans2.su;
        ans1.mx += ans2.su;
        return ans1;
    }
    Segment_tree(long long n, long long fill = -1) {
        tr.resize(4 * n);
        build(0, 0, n, fill);
    }
};

bool check(long long mid, vector<mnmx> a) {
    mnmx cur = mnmx(a.back().mn + 1, a.back().mx - 1);
    for (long long i = a.size() - mid - 1; i >= 0; i--) {
        cur = mnmx(cur.mn - 1, cur.mx + 1) + a[i + mid];
        if ((a[i].mx + mid) < cur.mn || cur.mx < (a[i].mn - mid)) continue;
        return true;
    }
    return false;
}

int sequence(int n, vector<int> a) {
    long long fans = 1;
    vector<vector<long long>> cnt(n);
    for (long long i = 0; i < n; i++) {
        a[i]--;
        cnt[a[i]].push_back(i);
    }
    Segment_tree tr(n);
    for (auto &i : cnt) {
        if (i.size() < 2) {
            for (auto &j : i) tr.upd(j, 1);
            continue;
        }
        long long m = i.size();
        for (auto &j : i) {
            tr.upd(j, 0);
        }
        vector<mnmx> pref, a;
        long long p = 0;
        for (auto &j : i) {
            auto tmp = tr.get2(p + 1, j);
            auto tmp2 = mnmx(tmp.mn, tmp.mx);
            a.push_back(tmp2);
            p = j;
        }
        auto tmp = tr.get2(p + 1, n);
        auto tmp2 = mnmx(tmp.mn, tmp.mx);
        a.push_back(tmp2);
        long long l = 1, r = m + 1;
        while (r - l > 1) {
            long long mid = (l + r) / 2;
            if (check(mid, a)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        fans = max(fans, l);
        for (auto &j : i) {
            tr.upd(j, 1);
        }
    }
    return fans;
}

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