Submission #985215

#	Time	Username	Problem	Language	Result	Execution time	Memory
985215		CrazyBotBoy	Sequence (APIO23_sequence)	C++17	11 / 100	2066 ms	36740 KiB

sequence

#include "sequence.h"
#include <vector>
#include <unordered_map>
#include <queue>
#include <iostream>

using namespace std;

class SlidingWindowMedian {
public:
    void add(int num) {
        if (maxHeap.empty() || num <= maxHeap.top()) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }
        balanceHeaps();
    }

    void remove(int num) {
        if (!maxHeap.empty() && num <= maxHeap.top()) {
            removedNums[num]++;
            if (num == maxHeap.top()) {
                removedCount++;
                maxHeap.pop();
            }
        } else if (!minHeap.empty() && num >= minHeap.top()) {
            removedNums[num]++;
            if (num == minHeap.top()) {
                removedCount++;
                minHeap.pop();
            }
        }
        balanceHeaps();
    }

    int getMedian() {
        return maxHeap.top();
    }

    void balanceHeaps() {
        while (!maxHeap.empty() && removedNums[maxHeap.top()]) {
            removedCount--;
            removedNums[maxHeap.top()]--;
            maxHeap.pop();
        }
        while (!minHeap.empty() && removedNums[minHeap.top()]) {
            removedCount--;
            removedNums[minHeap.top()]--;
            minHeap.pop();
        }
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

private:
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    unordered_map<int, int> removedNums;
    int removedCount = 0;
};

int sequence(int N, vector<int> A) {
    int maxOccurrences = 0;
    unordered_map<int, int> freq;
    SlidingWindowMedian swm;

    for (int l = 0; l < N; ++l) {
        freq.clear();
        swm = SlidingWindowMedian();

        for (int r = l; r < N; ++r) {
            swm.add(A[r]);
            freq[A[r]]++;

            int median = swm.getMedian();
            maxOccurrences = max(maxOccurrences, freq[median]);
        }
    }

    return maxOccurrences;
}

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