#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;
}
Compilation message
sequence.cpp: In member function 'void Sub4::FenwickTree::update(int, int)':
sequence.cpp:45:22: error: 'LASTBIT' was not declared in this scope
45 | i += LASTBIT(i);
| ^~~~~~~
sequence.cpp: In member function 'int Sub4::FenwickTree::get(int)':
sequence.cpp:53:22: error: 'LASTBIT' was not declared in this scope
53 | i -= LASTBIT(i);
| ^~~~~~~
sequence.cpp: In function 'int Sub4::edging(int, std::vector<int>)':
sequence.cpp:77:14: error: 'ALL' was not declared in this scope; did you mean 'P_ALL'?
77 | sort(ALL(pref), [] (array<int, 3> a, array<int, 3> b){
| ^~~
| P_ALL
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:144:21: error: 'ans' was not declared in this scope; did you mean 'abs'?
144 | if(p2 >= n / 2) ans = max(ans, p.second + desc[p.first]);
| ^~~
| abs
sequence.cpp:145:5: error: 'ans' was not declared in this scope; did you mean 'abs'?
145 | ans = max(ans, p.second);
| ^~~
| abs
sequence.cpp:149:21: error: 'ans' was not declared in this scope; did you mean 'abs'?
149 | if(p2 >= n / 2) ans = max(ans, p.second + asc[p.first]);
| ^~~
| abs
sequence.cpp:150:5: error: 'ans' was not declared in this scope; did you mean 'abs'?
150 | ans = max(ans, p.second);
| ^~~
| abs
sequence.cpp:152:10: error: 'ans' was not declared in this scope; did you mean 'abs'?
152 | return ans;
| ^~~
| abs
