Submission #985184

#	Time	Username	Problem	Language	Result	Execution time	Memory
985184		Kracken_180	Sequence (APIO23_sequence)	C++17	28 / 100	2019 ms	2097152 KiB

sequence

#include "sequence.h"
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
int sequence(int N, vector<int> A) {
    vector<unordered_map<int, int>> prefixFreq(N + 1);
    for (int i = 0; i < N; ++i) {
        prefixFreq[i + 1] = prefixFreq[i];
        prefixFreq[i + 1][A[i]]++;
    }
 
    int maxOccurrences = 0;
    for (int l = 0; l < N; ++l) {
        multiset<int> leftSet, rightSet;
        unordered_map<int, int> freq;
        for (int r = l; r < N; ++r) {
            if (leftSet.empty() || A[r] <= *leftSet.rbegin()) {
                leftSet.insert(A[r]);
            } else {
                rightSet.insert(A[r]);
            }
 
            while (leftSet.size() > rightSet.size() + 1) {
                rightSet.insert(*leftSet.rbegin());
                leftSet.erase(prev(leftSet.end()));
            }
 
            while (rightSet.size() > leftSet.size()) {
                leftSet.insert(*rightSet.begin());
                rightSet.erase(rightSet.begin());
            }
 
            int median1 = *leftSet.rbegin();
            int median2 = (leftSet.size() + rightSet.size()) % 2 == 0 ? *rightSet.begin() : median1;
 
            freq[A[r]]++;
            maxOccurrences = max(maxOccurrences, freq[median1]);
            if (median1 != median2) {
                maxOccurrences = max(maxOccurrences, freq[median2]);
            }
        }
    }
 
    return maxOccurrences;
}

• 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