| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1328707 | nguyenkhangninh99 | Sequence (APIO23_sequence) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
int sequence(int n, vector<int> c){
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) a[i] = c[i - 1];
vector<vector<int>> pos(n + 1);
for(int i = 1; i <= n; i++) pos[a[i]].push_back(i);
vector<int> pre(n + 1);
int ans = 1;
for(int val = 1; val <= n; val++){
for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] + (a[i] > val) - (a[i] < val);
vector<int> premn(n + 2), premx(n + 2);
for(int i = 1; i <= n; i++){
premn[i] = min(premn[i - 1], pre[i]);
premx[i] = max(premx[i - 1], pre[i]);
}
vector<int> sufmn(n + 2), sufmx(n + 2);
sufmn[n + 1] = 1e9, sufmx[n + 1] = -1e9;
for(int i = n; i >= 1; i--){
sufmn[i] = min(sufmn[i + 1], pre[i]);
sufmx[i] = max(sufmx[i + 1], pre[i]);
}
auto ok = [&](int l1, int r1, int l2, int r2, int len) -> bool {
if(max(l1, l2) <= min(r1, r2)) return true;
else return (max(l1 - r2, l2 - r1) <= len);
};
for(int i = 0; i < pos[val].size(); i++){
for(int j = i + 1; j < pos[val].size(); j++){
int l = pos[val][i] - 1, r = pos[val][j];
if(ok(premn[l], premx[l], sufmn[r], sufmx[r], j - i + 1)){
ans = max(ans, j - i + 1);
}
}
}
}
return ans;
}
#ifdef LOCAL
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int> a(n);
for(int &x: a) cin >> x;
cout << sequence(n, a);
}
#endif LOCAL