Submission #1156978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156978		The_Samurai	Sequence (APIO23_sequence)	C++20	28 / 100	2096 ms	29772 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;
    }
};

template<typename T> struct Fenwick {
    int n;
    vector<T> tree;

    void init(int len) {
        n = len;
        tree.assign(n + 1, 0);
    }

    void update(int i, T v) {
        for (i++; i <= n; i += i & (-i)) tree[i] += v;
    }

    T get(int i) {
        T sum = 0;
        for (i++; i > 0; i -= i & (-i)) sum += tree[i];
        return sum;
    }

    T get(int l, int r) {
        return get(r) - get(l - 1);
    }
};


int sequence(int n, vector<int> a) {
    int ans = 1;
    for (int l = 0; l < n; l++) {
        Fenwick<int> fw; fw.init(n + 1);
        fw.update(a[l], 1);
        set<int> st; st.insert(a[l]);
        int mid = a[l], ln = 1;

        for (int r = l + 1; r < n; r++) {
            ln++;
            fw.update(a[r], 1);
            st.insert(a[r]);
            auto it = st.lower_bound(mid);
            for (int j = 0; j < 3 and it != st.begin(); j++, it--);
            bool found = false;
            for (int j = 0; j < 6 and it != st.end(); j++, it++) {
                int prev = fw.get(*it - 1);
                int now = fw.get(*it);
                bool ok = false;
                ok |= prev < (ln + 1) / 2 and now >= (ln + 1) / 2;
                ok |= prev < (ln + 2) / 2 and now >= (ln + 2) / 2;
                if (ok) {
                    // cout << l << ' ' << r << ' ' << *it << ' ' << now - prev << endl;
                    ans = max(ans, now - prev);
                    mid = *it;
                    found = true;
                }
            }
            assert(found);
        }
    }

    return ans;
}

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