Submission #982575

#	Time	Username	Problem	Language	Result	Execution time	Memory
982575		Ghetto	Sequence (APIO23_sequence)	C++17	28 / 100	2070 ms	51016 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 5;

int n;
int a[MAX_N];
int sequence(int tmp_n, vector<int> tmp_a) {
    n = tmp_n;
    for (int i = 0; i < n; i++) a[i + 1] = tmp_a[i];

    int ans = 1;
    for (int l = 1; l <= n; l++) {
        unordered_map<int, int> freq;
        multiset<int> smalls, bigs;
        for (int r = l; r <= n; r++) {
            freq[a[r]]++;

            if (smalls.empty() || a[r] <= *smalls.rbegin()) smalls.insert(a[r]);
            else bigs.insert(a[r]);

            while (bigs.size() > smalls.size()) 
                smalls.insert(*bigs.begin()), bigs.erase(bigs.begin());
            while (smalls.size() > bigs.size() + 1)
                bigs.insert(*smalls.rbegin()), smalls.erase(next(smalls.end(), -1));
            
            vector<int> medians = {*smalls.rbegin()};
            if (bigs.size() && bigs.size() == smalls.size()) medians.push_back(*bigs.begin());
            for (int x : medians) ans = max(ans, freq[x]);
        }
    }
    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