| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1062041 | 2024-08-16T17:36:43 Z | KasymK | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 KB |
#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;
}