#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
struct ST{
vector<int> a;
int n;
ST(int ns){
n = ns;
a.resize(n + 1);
}
void add(int l, int r, int x){
for (int i = l; i <= r; i++){
a[i] += x;
}
}
pii get(int l, int r){
pii out = {1e9, 0};
for (int i = l; i <= r; i++){
out.ff = min(out.ff, a[i]);
out.ss = max(out.ss, a[i]);
}
return out;
}
};
int sequence(int n, vector<int> a){
a.insert(a.begin(), 0);
vector<int> d[n + 1];
for (int i = 1; i <= n; i++) d[a[i]].pb(i);
ST T(n);
for (int i = 1; i <= n; i++) T.add(i, n, 1);
int out = 1;
for (int x = 1; x <= n; x++){
if (d[x].empty()) continue;
for (int j: d[x]) T.add(j, n, -1); // a[j] = 0
vector<pii> all;
all.pb({0, d[x][0] - 1});
// [0, d[x][0] - 1]
for (int i = 0; i + 1 < d[x].size(); i++){
all.pb({d[x][i], d[x][i + 1] - 1});
// [d[x][i], d[x][i + 1] - 1]
}
all.pb({d[x].back(), n});
// [d[x].back(), n]
for (auto &[l, r]: all){
pii f = T.get(l, r);
l = f.ff; r = f.ss;
}
for (int i = 0; i < all.size(); i++){
for (int j = i + 1; j < all.size(); j++){
if (i + all[i].ff <= j + all[j].ss && i - all[i].ss <= j - all[j].ff){
out = max(out, j - i);
}
}
}
for (int j: d[x]) T.add(j, n, -1); // a[j] = -1
}
// -e <= h - l <= e
// 0 <= i < j;
// [li, ri]; [lj, rj];
// h - l: [lj - ri, rj - li]
// inter [i - j, j - i] is not empty
// max(i - j, lj - ri) <= min(rj - li, j - i);
// i - j <= rj - li <-> i + li <= rj + j
// lj - ri <= j - i <-> i - ri <= j - lj
return out;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |