| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 954323 | Trisanu_Das | Sequence (APIO23_sequence) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "sequence.h"
using namespace std;
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T& container, char separator = ' ', char finish = '\n'){
for(auto item: container) cout << item << separator;
cout << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
namespace Sub4{
const int INF = 1e9 + 69;
struct FenwickTree{
int n;
vector<int> a;
FenwickTree(int _n){
n = _n;
a.resize(n+1, INF);
}
void update(int i, int v){
while(i <= n){
minimize(a[i], v);
i += LASTBIT(i);
}
}
int get(int i){
int ans = INF;
while(i > 0){
minimize(ans, a[i]);
i -= LASTBIT(i);
}
return ans;
}
};
bool check(vector<int> a){
for(int i: a) if (i > 3) return 0;
return 1;
}
int edging(int n, vector<int> a){
int ans = 0;
vector<array<int, 3>> pref(n+1, {{0, n+1, n+1}});
a.insert(a.begin(), -1);
for(int i = 1; i<=n; ++i){
pref[i] = pref[i-1];
if (a[i] == 1) pref[i][0]++;
if (a[i] < 1) pref[i][1]--;
else pref[i][1]++;
if (a[i] <= 1) pref[i][2]++;
else pref[i][2]--;
}
sort(ALL(pref), [] (array<int, 3> a, array<int, 3> b){
if (a[2] != b[2]) return a[2] < b[2];
return a[1] < b[1];
});
FenwickTree bit(n * 2 + 2);
for(auto i: pref){
maximize(ans, i[0] - bit.get(i[1] - 1));
bit.update(i[1], i[0]);
}
return ans;
}
int solve(int n, vector<int> a){
int ans = 0;
for(int i = 1; i<=3; ++i){
vector<int> b = a;
for(int &j: b){
if (j < i) j = 0;
else if (j == i) j = 1;
else j = 2;
}
maximize(ans, edging(n, b));
}
return ans;
}
}
int sequence(int n, vector<int> a){
if(n <= 2000){
int occ[n + 1], ans = 0;
for(int i = 0; i < n; i++){
memset(occ, 0, sizeof(occ));
multiset<int> l, r;
for(int j = i; j < n; j++){
occ[a[j]]++;
if(r.empty() || a[j] <= *r.begin()) l.insert(a[j]);
else r.insert(a[j]);
if(l.size() > r.size() + 1){
r.insert(*--l.end());
l.erase(--l.end());
}
if(r.size() > l.size()){
l.insert(*r.begin());
r.erase(r.begin());
}
ans = max(ans, occ[*--l.end()]);
if(l.size() == r.size()) ans = max(ans, occ[*r.begin()]);
}
}
return ans;
}
if(Sub4::check(a)) return Sub4::solve(n, a);
map<int, int> asc, desc;
bool flag = true;
for(int i = 0; i < n; i++){
if(flag) asc[a[i]]++;
else desc[a[i]]++;
if(i && a[i] < a[i - 1]) flag = false;
}
sort(a.begin(), a.end());
for(auto p : asc){
auto p2 = lower_bound(a.begin(), a.end(), p.first) - a.begin();
if(p2 >= n / 2) ans = max(ans, p.second + desc[p.first]);
ans = max(ans, p.second);
}
for(auto p : desc){
auto p2 = lower_bound(a.begin(), a.end(), p.first) - a.begin();
if(p2 >= n / 2) ans = max(ans, p.second + asc[p.first]);
ans = max(ans, p.second);
}
return ans;
}