Submission #1062042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062042		KasymK	Sequence (APIO23_sequence)	C++17	11 / 100	2044 ms	52168 KiB

sequence

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second   
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}

int sequence(int n, vector<int> v){
    int answer = 0;
    unordered_map<int, int> freq;
    multiset<int> left, right;
    auto add = [&](int x) {
        freq[x]++;
        if (!right.empty() && x >= *right.begin()) {
            right.insert(x);
        } else {
            left.insert(x);
        }

        // Balance the left and right sets to maintain equal sizes
        if (left.size() > right.size() + 1) {
            right.insert(*left.rbegin());
            left.erase(--left.end());
        } else if (right.size() > left.size()) {
            left.insert(*right.begin());
            right.erase(right.begin());
        }
    };

    auto remove = [&](int x) {
        if (x >= *right.begin()) {
            right.erase(right.find(x));
        } else {
            left.erase(left.find(x));
        }
        freq[x]--;
        if (freq[x] == 0) freq.erase(x);

        // Rebalance the sets
        if (left.size() > right.size() + 1) {
            right.insert(*left.rbegin());
            left.erase(--left.end());
        } else if (right.size() > left.size()) {
            left.insert(*right.begin());
            right.erase(right.begin());
        }
    };

    for (int i = 0; i < n; ++i) {
        left.clear();
        right.clear();
        freq.clear();
        for (int j = i; j < n; ++j) {
            add(v[j]);

            int median1 = *left.rbegin();
            int median2 = right.empty() ? median1 : *right.begin();

            // Get the maximum frequency of median1 and median2
            umax(answer, max(freq[median1], freq[median2]));
        }
    }
    return answer;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:35:10: warning: variable 'remove' set but not used [-Wunused-but-set-variable]
   35 |     auto remove = [&](int x) {
      |          ^~~~~~

• 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