#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 5e5 + 100;
const int M = 2e6;
struct FT{
vector <int> f;
int N;
FT(int n) {
N = n;
f.assign(n + 1, 0);
}
void upd(int i, int x) {
for (; i <= N; i += i & (-i))
f[i] += x;
}
int get(int i) {
int s = 0;
for (; i; i -= i & (-i))
s += f[i];
return s;
}
};
struct fen{
vector <int> f;
int N;
fen(int n) {
N = n;
f.assign(n + 1, 1e9);
}
void upd(int i, int x) {
i++;
for (; i; i -= i & (-i))
f[i] = min(f[i], x);
}
int get(int i) {
i++;
int s = f[i];
while (i <= N) {
s = min(s, f[i]);
i += i & (-i);
}
return s;
}
};
vector <int> pos[N];
int a[N], n;
int get(int add) {
fen F(n * 4 + 100);
FT P(n + 4);
for (int i = 1; i <= n; i++) {
P.upd(i, add);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (auto x : pos[i]) {
P.upd(x, -add);
}
vector <pair <int, int>> st;
for (int j = 0; j < sz(pos[i]); j++) {
if (j && pos[i][j] - 1 != pos[i][j - 1])
st.pb({j, P.get(pos[i][j] - 1)});
st.pb({j + 1, P.get(pos[i][j])});
if (j < sz(pos[i]) - 1 && pos[i][j] + 1 != pos[i][j + 1])
st.pb({j + 1, P.get(pos[i][j] + 1)});
}
st.pb({0, 0});
st.pb({sz(pos[i]), P.get(n)});
uniquev(st);
sort(all(st), [&] (pair <int, int> &A, pair <int, int> &B) {return A.s < B.s;} );
for (auto x : st) {
ans = max(ans, x.f - F.get(x.s - x.f + n));
F.upd(x.s - x.f + n, x.f);
}
for (auto x : pos[i]) {
P.upd(x, -add);
}
}
return ans;
}
int sequence(int N, vector <int> A) {
n = N;
for (int i = 1; i <= n; i++) {
a[i] = A[i - 1];
pos[a[i]].pb(i);
}
int ans = get(1);
for (int i = 1; i <= n; i++)
pos[i].clear();
return ans;
}
/*int main() {
cout << sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2}) << '\n';
cout << sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1}) << '\n';
cout << sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2}) << '\n';
return 0;
}*/
// s[i] - s[j] <= p[i] - p[j]
// s[i] - p[i] <= s[j] - p[j]
// s[i] - i >= s[j] - j
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
13912 KB |
Output is correct |
2 |
Correct |
3 ms |
13916 KB |
Output is correct |
3 |
Correct |
3 ms |
13912 KB |
Output is correct |
4 |
Incorrect |
3 ms |
13916 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
13912 KB |
Output is correct |
2 |
Correct |
3 ms |
13916 KB |
Output is correct |
3 |
Correct |
3 ms |
13912 KB |
Output is correct |
4 |
Incorrect |
3 ms |
13916 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
13912 KB |
Output is correct |
2 |
Correct |
223 ms |
39560 KB |
Output is correct |
3 |
Correct |
231 ms |
39548 KB |
Output is correct |
4 |
Correct |
146 ms |
32332 KB |
Output is correct |
5 |
Incorrect |
203 ms |
40016 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
13916 KB |
Output is correct |
2 |
Correct |
229 ms |
41808 KB |
Output is correct |
3 |
Incorrect |
217 ms |
38720 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
232 ms |
45284 KB |
Output is correct |
2 |
Correct |
260 ms |
45460 KB |
Output is correct |
3 |
Incorrect |
234 ms |
44624 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
13912 KB |
Output is correct |
2 |
Correct |
3 ms |
13916 KB |
Output is correct |
3 |
Correct |
3 ms |
13912 KB |
Output is correct |
4 |
Incorrect |
3 ms |
13916 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
13912 KB |
Output is correct |
2 |
Correct |
3 ms |
13916 KB |
Output is correct |
3 |
Correct |
3 ms |
13912 KB |
Output is correct |
4 |
Incorrect |
3 ms |
13916 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |