Submission #1144153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144153		AlgorithmWarrior	Sequence (APIO23_sequence)	C++20	Compilation error	0 ms	0 KiB

sequence

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

// Clasa MedianHeap pentru a menține medianele eficient
class MedianHeap {
private:
    priority_queue<int> leftMaxHeap; // Max-heap pentru jumătatea mai mică
    priority_queue<int, vector<int>, greater<int>> rightMinHeap; // Min-heap pentru jumătatea mai mare

public:
    void insert(int num) {
        if (leftMaxHeap.empty() || num <= leftMaxHeap.top()) {
            leftMaxHeap.push(num);
        } else {
            rightMinHeap.push(num);
        }

        // Rebalansare pentru a menține echilibrul dintre cele două heap-uri
        if (leftMaxHeap.size() > rightMinHeap.size() + 1) {
            rightMinHeap.push(leftMaxHeap.top());
            leftMaxHeap.pop();
        } else if (rightMinHeap.size() > leftMaxHeap.size()) {
            leftMaxHeap.push(rightMinHeap.top());
            rightMinHeap.pop();
        }
    }

    void remove(int num) {
        if (!leftMaxHeap.empty() && num <= leftMaxHeap.top()) {
            leftMaxHeap.pop();
        } else {
            rightMinHeap.pop();
        }

        // Rebalansare
        if (leftMaxHeap.size() > rightMinHeap.size() + 1) {
            rightMinHeap.push(leftMaxHeap.top());
            leftMaxHeap.pop();
        } else if (rightMinHeap.size() > leftMaxHeap.size()) {
            leftMaxHeap.push(rightMinHeap.top());
            rightMinHeap.pop();
        }
    }

    int getMedian() {
        return leftMaxHeap.top(); // Mediană este mereu în vârful max-heap-ului
    }

    void clear() {
        while (!leftMaxHeap.empty()) leftMaxHeap.pop();
        while (!rightMinHeap.empty()) rightMinHeap.pop();
    }
};

int solveSequence(int n, vector<int>& arr) {
    int max_freq = 0;
    unordered_map<int, int> freq_map; // Pentru a stoca frecvențele medianelor

    // Parcurgem fiecare subsecvență (l, r)
    for (int l = 0; l < n; ++l) {
        MedianHeap medianHeap;
        freq_map.clear();

        for (int r = l; r < n; ++r) {
            medianHeap.insert(arr[r]);
            int median = medianHeap.getMedian();
            
            freq_map[median]++;
            max_freq = max(max_freq, freq_map[median]);
        }
    }

    return max_freq;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    cout << solveSequence(n, arr) << endl;
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccDda7zS.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc38UGcv.o:sequence.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccDda7zS.o: in function `main':
grader.cpp:(.text.startup+0x2c7): undefined reference to `sequence(int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status