Submission #1191353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191353		just	Sequence (APIO23_sequence)	C++20	35 / 100	1035 ms	59124 KiB

sequence

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<
    T,
    null_type,
    less<T>,
    rb_tree_tag,
    tree_order_statistics_node_update
>;

#define vec vector
#define all(x) (x).begin(), (x).end()

int sequence(int N, std::vector<int> A) {
    if (N <= 2000) {
        int ans = 0;
        for(int i = 0; i < N; i++) {
            auto tree = ordered_set<pair<int,int>>();
            map<int,int> f;
            for(int j = i; j < N; j++) {
                tree.insert({A[j], j});
                f[A[j]]++;

                if (tree.size() % 2 == 0) {
                    int a = tree.find_by_order(tree.size() / 2 - 1)->first;
                    int b = tree.find_by_order(tree.size() / 2)->first;
                    ans = max(ans, f[a]);
                    ans = max(ans, f[b]);
                } else {
                    int a = tree.find_by_order(tree.size() / 2)->first;
                    ans = max(ans, f[a]);
                }
            }
        }

        return ans;
    }

    int ans = 0;
    int i = max_element(all(A)) - A.begin();
    int l = i, r = i;

    ordered_set<pair<int,int>> tree;
    map<int,int> f;

    while (l > 0 || r < N - 1) {
        bool right = 0, left = 0;
        if (l == 0) right = 1;
        else if (r == N - 1) left = 1;
        else if (A[l - 1] > A[r + 1]) left = 1;
        else right = 1;

        if (right) {
            r++;
            tree.insert({A[r], r});
            f[A[r]]++;
        } else if (left) {
            l--;
            tree.insert({A[l], l});
            f[A[l]]++;
        }

        if (tree.size() % 2 == 0) {
            int a = tree.find_by_order(tree.size() / 2 - 1)->first;
            int b = tree.find_by_order(tree.size() / 2)->first;
            ans = max(ans, f[a]);
            ans = max(ans, f[b]);
        } else {
            int a = tree.find_by_order(tree.size() / 2)->first;
            ans = max(ans, f[a]);
        }
    }

    f.clear();
    for (int j = 0; j < N; j++) {
        if (j == i) f.clear();
        f[A[j]]++;
        ans = max(ans, f[A[j]]);
    }

    return ans;
}

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