Submission #1156966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156966		The_Samurai	Sequence (APIO23_sequence)	C++20	12 / 100	115 ms	24296 KiB

sequence

#include "sequence.h"
#include "bits/stdc++.h"
using namespace std;

template<typename T> struct SegTree {
    vector<T> tree;
    int size;
    T neutral_element = 1e9; // sum - 0, mx - (-INF), mn - INF

    inline T merge(T a, T b) {
        return min(a, b);
    }

    void init(int n) {
        size = 1;
        while (size <= n) size *= 2;
        tree.assign(2 * size, neutral_element);
    }

    void build(vector<T> &a) {
        size = 1;
        while (size < a.size()) size *= 2;
        tree.assign(2 * size, neutral_element);
        for (int i = size; i < size + a.size(); i++) tree[i] = a[i - size];
        for (int i = size - 1; i > 0; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
    }

    void upd(int p, T value) {  // upd value at position p
        p += size;
        tree[p] = merge(value, tree[p]);
        for (; p > 1; p >>= 1) tree[p >> 1] = merge(tree[p], tree[p ^ 1]);
    }

    T get(int l, int r) {  // sum on interval [l, r]
        if (l > r) return neutral_element;
        T res = neutral_element;
        for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = merge(res, tree[l++]);
            if (r & 1) res = merge(res, tree[--r]);
        }
        return res;
    }
};


int sequence(int n, vector<int> a) {
    auto b = a;
    sort(b.begin(), b.end());

    int ans = count(b.begin(), b.end(), b[(n - 1) / 2]);
    ans = max(ans, (int) count(b.begin(), b.end(), b[n / 2]));

    vector pref(4, vector(n, 0));
    for (int i = 0; i < n; i++) pref[a[i]][i]++;
    for (int v = 1; v <= 3; v++) for (int i = 1; i < n; i++) pref[v][i] += pref[v][i - 1];
    
    for (int v = 1; v <= 3; v++) {
        if (v == 2) continue;
        vector<int> val(n);
        for (int i = 0; i < n; i++) val[i] = a[i] == v ? 1 : -1;
        SegTree<int> sg; sg.init(2 * n + 1);
        sg.upd(n, -1);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += val[i];
            int pos = sg.get(0, sum + n);
            sg.upd(sum + n, i);
            if (pos < n) {
                ans = max(ans, pref[v][i] - (pos > 0 ? pref[v][pos - 1] : 0));
            }
        }
    }

    return ans;
}

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