#ifndef LOCAL
#pragma GCC optimize("O2")
#pragma GCC target("avx2")
#include "sequence.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define dbg(...)
#define STRUCT_DBG(...)
#else
#include "lib/debug.h"
#endif
using namespace std;
using namespace __gnu_pbds;
using ll = int;
using ld = long double;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
using vll = vector<ll>;
using vpll = vector<pair<ll, ll>>;
using vvll = vector<vector<ll>>;
using vvpll = vector<vector<pair<ll, ll>>>;
template <class T>
using indexed_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define RFOR(i, e, s) for (ll i = (ll)e - 1; i >= (ll)s; i--)
#define TRAV(a, c) for (const auto &a : c)
#define all(x) x.begin(), x.end()
const ll MXN = 5e5 + 5;
ll n, suffmx[2 * MXN], suffmn[2 * MXN], prefmx[2 * MXN], prefmn[2 * MXN],
lsuff[2 * MXN], lprefmx[2 * MXN], lprefmn[2 * MXN];
vec<ll> inds[MXN];
#define lc(x) x + 1
#define rc(x) x + ((tm - tl + 1) << 1ll)
inline void pullsuff(ll v, ll tl, ll tr) {
if (tl == tr) return;
ll tm = (tl + tr) >> 1ll;
suffmx[v] = max(suffmx[lc(v)], suffmx[rc(v)]);
suffmn[v] = min(suffmn[lc(v)], suffmn[rc(v)]);
}
inline void pullpref(ll v, ll tl, ll tr) {
if (tl == tr) return;
ll tm = (tl + tr) >> 1ll;
prefmx[v] = max(prefmx[lc(v)], prefmx[rc(v)]);
prefmn[v] = min(prefmn[lc(v)], prefmn[rc(v)]);
}
inline void pushsuff(ll v, ll tl, ll tr) {
if (!lsuff[v]) return;
ll tm = (tl + tr) >> 1ll;
suffmx[v] += lsuff[v];
suffmn[v] += lsuff[v];
if (tl != tr) {
lsuff[lc(v)] += lsuff[v];
lsuff[rc(v)] += lsuff[v];
}
lsuff[v] = 0;
}
inline void pushpref(ll v, ll tl, ll tr) {
if (!lprefmx[v] && !lprefmn[v]) return;
ll tm = (tl + tr) >> 1ll;
prefmx[v] += lprefmx[v];
prefmn[v] += lprefmn[v];
if (tl != tr) {
lprefmx[lc(v)] += lprefmx[v];
lprefmx[rc(v)] += lprefmx[v];
lprefmn[lc(v)] += lprefmn[v];
lprefmn[rc(v)] += lprefmn[v];
}
lprefmx[v] = lprefmn[v] = 0;
}
void build(ll v, ll tl, ll tr) {
if (tl == tr) {
suffmx[v] = suffmn[v] = n - tl;
prefmx[v] = prefmn[v] = tl + 1;
} else {
ll tm = (tl + tr) >> 1ll;
build(lc(v), tl, tm);
build(rc(v), tm + 1, tr);
pullsuff(v, tl, tr);
pullpref(v, tl, tr);
}
}
void update_suff(ll v, ll tl, ll tr, ll r, ll x) {
ll tm = (tl + tr) >> 1ll;
pushsuff(v, tl, tr);
if (r < tl) return;
if (tr <= r) {
lsuff[v] += x;
pushsuff(v, tl, tr);
} else {
update_suff(lc(v), tl, tm, r, x);
if (tm + 1 <= r) {
update_suff(rc(v), tm + 1, tr, r, x);
} else {
pushsuff(rc(v), tm + 1, tr);
}
pullsuff(v, tl, tr);
}
}
void update_prefmx(ll v, ll tl, ll tr, ll l, ll x) {
ll tm = (tl + tr) >> 1ll;
pushpref(v, tl, tr);
if (tr < l) return;
if (l <= tl) {
lprefmx[v] += x;
pushpref(v, tl, tr);
} else {
if (tm >= l) {
update_prefmx(lc(v), tl, tm, l, x);
} else {
pushpref(lc(v), tl, tm);
}
update_prefmx(rc(v), tm + 1, tr, l, x);
pullpref(v, tl, tr);
}
}
void update_prefmn(ll v, ll tl, ll tr, ll l, ll x) {
ll tm = (tl + tr) >> 1ll;
pushpref(v, tl, tr);
if (tr < l) return;
if (l <= tl) {
lprefmn[v] += x;
pushpref(v, tl, tr);
} else {
if (tm >= l) {
update_prefmn(lc(v), tl, tm, l, x);
} else {
pushpref(lc(v), tl, tm);
}
update_prefmn(rc(v), tm + 1, tr, l, x);
pullpref(v, tl, tr);
}
}
inline void one_to_zero(ll ind) {
update_suff(0, 0, n - 1, ind, -1);
update_prefmn(0, 0, n - 1, ind, -2);
}
inline void zero_to_negone(ll ind) {
update_suff(0, 0, n - 1, ind, -1);
update_prefmx(0, 0, n - 1, ind, -2);
}
const pll query_suff(ll v, ll tl, ll tr, ll r) {
ll tm = (tl + tr) >> 1ll;
pushsuff(v, tl, tr);
if (r < tl) return {INT_MAX, INT_MIN};
if (tr <= r) {
return {suffmn[v], suffmx[v]};
} else {
pll o1 = query_suff(lc(v), tl, tm, r);
pll o2 = (tm + 1 <= r) ? query_suff(rc(v), tm + 1, tr, r)
: pll{INT_MAX, INT_MIN};
return {min(o1.first, o2.first), {max(o1.second, o2.second)}};
}
}
const vll query_point(ll v, ll tl, ll tr, ll ind) {
ll tm = (tl + tr) >> 1ll;
pushpref(v, tl, tr);
pushsuff(v, tl, tr);
if (tl == tr && tl == ind) {
return {prefmn[v], prefmx[v], suffmn[v], suffmx[v]};
} else {
if (ind <= tm) {
return query_point(lc(v), tl, tm, ind);
} else {
return query_point(rc(v), tm + 1, tr, ind);
}
}
};
ll walk_pref(ll v, ll tl, ll tr, ll l, ll r, ll la, ll ra) {
ll tm = (tl + tr) >> 1ll;
pushpref(v, tl, tr);
if (r < tl || tr < l || !(la <= prefmx[v] && prefmn[v] <= ra)) return l;
if (tl == tr) return tl;
ll o = walk_pref(rc(v), tm + 1, tr, l, r, la, ra);
if (o != l) return o;
return walk_pref(lc(v), tl, tm, l, r, la, ra);
};
int sequence(int _n, vector<int> a) {
n = _n;
FOR(i, 0, n) inds[a[i]].push_back(i);
build(0, 0, n - 1);
ll ans = 0;
CFOR(i, 1, n) {
if (inds[i].empty()) continue;
TRAV(e, inds[i]) one_to_zero(e);
TRAV(e, inds[i]) {
auto o1 = query_suff(0, 0, n - 1, e);
auto o2 = query_point(0, 0, n - 1, e);
ll la = -(o1.first - o2[2] - o2[0]) + 1;
ll ra = -(o1.second - o2[3] - o2[1]) - 1;
swap(la, ra);
ll best = walk_pref(0, 0, n - 1, e, n - 1, la, ra);
auto it1 = upper_bound(all(inds[i]), best);
auto it2 = lower_bound(all(inds[i]), e);
ans = max(ans, (ll)(it1 - it2));
}
TRAV(e, inds[i]) zero_to_negone(e);
}
return ans;
}
// int main() {
// int N;
// assert(1 == scanf("%d", &N));
// std::vector<int> A(N);
// for (int i = 0; i < N; ++i) {
// assert(1 == scanf("%d", &A[i]));
// }
// int result = sequence(N, A);
// printf("%d\n", result);
// return 0;
// }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
21084 KB |
Output is correct |
2 |
Correct |
7 ms |
21084 KB |
Output is correct |
3 |
Correct |
5 ms |
21332 KB |
Output is correct |
4 |
Correct |
6 ms |
21336 KB |
Output is correct |
5 |
Correct |
5 ms |
21080 KB |
Output is correct |
6 |
Correct |
5 ms |
21340 KB |
Output is correct |
7 |
Correct |
5 ms |
21080 KB |
Output is correct |
8 |
Correct |
5 ms |
21084 KB |
Output is correct |
9 |
Correct |
5 ms |
21116 KB |
Output is correct |
10 |
Correct |
5 ms |
21084 KB |
Output is correct |
11 |
Correct |
5 ms |
21080 KB |
Output is correct |
12 |
Correct |
5 ms |
21084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
21084 KB |
Output is correct |
2 |
Correct |
7 ms |
21084 KB |
Output is correct |
3 |
Correct |
5 ms |
21332 KB |
Output is correct |
4 |
Correct |
6 ms |
21336 KB |
Output is correct |
5 |
Correct |
5 ms |
21080 KB |
Output is correct |
6 |
Correct |
5 ms |
21340 KB |
Output is correct |
7 |
Correct |
5 ms |
21080 KB |
Output is correct |
8 |
Correct |
5 ms |
21084 KB |
Output is correct |
9 |
Correct |
5 ms |
21116 KB |
Output is correct |
10 |
Correct |
5 ms |
21084 KB |
Output is correct |
11 |
Correct |
5 ms |
21080 KB |
Output is correct |
12 |
Correct |
5 ms |
21084 KB |
Output is correct |
13 |
Correct |
7 ms |
21080 KB |
Output is correct |
14 |
Correct |
7 ms |
21084 KB |
Output is correct |
15 |
Correct |
7 ms |
21084 KB |
Output is correct |
16 |
Correct |
7 ms |
21084 KB |
Output is correct |
17 |
Correct |
6 ms |
21084 KB |
Output is correct |
18 |
Correct |
6 ms |
21084 KB |
Output is correct |
19 |
Correct |
7 ms |
21196 KB |
Output is correct |
20 |
Correct |
7 ms |
21124 KB |
Output is correct |
21 |
Correct |
7 ms |
21084 KB |
Output is correct |
22 |
Correct |
8 ms |
21084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
21084 KB |
Output is correct |
2 |
Correct |
684 ms |
56568 KB |
Output is correct |
3 |
Correct |
690 ms |
56532 KB |
Output is correct |
4 |
Correct |
626 ms |
46772 KB |
Output is correct |
5 |
Correct |
671 ms |
55728 KB |
Output is correct |
6 |
Correct |
655 ms |
55600 KB |
Output is correct |
7 |
Correct |
619 ms |
47192 KB |
Output is correct |
8 |
Correct |
606 ms |
47400 KB |
Output is correct |
9 |
Correct |
608 ms |
46640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
21084 KB |
Output is correct |
2 |
Correct |
640 ms |
46692 KB |
Output is correct |
3 |
Correct |
725 ms |
46564 KB |
Output is correct |
4 |
Correct |
646 ms |
46520 KB |
Output is correct |
5 |
Correct |
662 ms |
46580 KB |
Output is correct |
6 |
Correct |
616 ms |
46640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
970 ms |
62332 KB |
Output is correct |
2 |
Correct |
954 ms |
62476 KB |
Output is correct |
3 |
Correct |
1006 ms |
61852 KB |
Output is correct |
4 |
Correct |
933 ms |
61780 KB |
Output is correct |
5 |
Correct |
880 ms |
58432 KB |
Output is correct |
6 |
Correct |
836 ms |
58432 KB |
Output is correct |
7 |
Correct |
702 ms |
57168 KB |
Output is correct |
8 |
Correct |
685 ms |
56912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
21084 KB |
Output is correct |
2 |
Correct |
7 ms |
21084 KB |
Output is correct |
3 |
Correct |
5 ms |
21332 KB |
Output is correct |
4 |
Correct |
6 ms |
21336 KB |
Output is correct |
5 |
Correct |
5 ms |
21080 KB |
Output is correct |
6 |
Correct |
5 ms |
21340 KB |
Output is correct |
7 |
Correct |
5 ms |
21080 KB |
Output is correct |
8 |
Correct |
5 ms |
21084 KB |
Output is correct |
9 |
Correct |
5 ms |
21116 KB |
Output is correct |
10 |
Correct |
5 ms |
21084 KB |
Output is correct |
11 |
Correct |
5 ms |
21080 KB |
Output is correct |
12 |
Correct |
5 ms |
21084 KB |
Output is correct |
13 |
Correct |
7 ms |
21080 KB |
Output is correct |
14 |
Correct |
7 ms |
21084 KB |
Output is correct |
15 |
Correct |
7 ms |
21084 KB |
Output is correct |
16 |
Correct |
7 ms |
21084 KB |
Output is correct |
17 |
Correct |
6 ms |
21084 KB |
Output is correct |
18 |
Correct |
6 ms |
21084 KB |
Output is correct |
19 |
Correct |
7 ms |
21196 KB |
Output is correct |
20 |
Correct |
7 ms |
21124 KB |
Output is correct |
21 |
Correct |
7 ms |
21084 KB |
Output is correct |
22 |
Correct |
8 ms |
21084 KB |
Output is correct |
23 |
Correct |
133 ms |
24920 KB |
Output is correct |
24 |
Correct |
135 ms |
24920 KB |
Output is correct |
25 |
Correct |
134 ms |
24924 KB |
Output is correct |
26 |
Correct |
143 ms |
23868 KB |
Output is correct |
27 |
Correct |
127 ms |
23896 KB |
Output is correct |
28 |
Correct |
126 ms |
23976 KB |
Output is correct |
29 |
Correct |
110 ms |
23384 KB |
Output is correct |
30 |
Correct |
97 ms |
23640 KB |
Output is correct |
31 |
Correct |
87 ms |
23752 KB |
Output is correct |
32 |
Correct |
91 ms |
25936 KB |
Output is correct |
33 |
Correct |
158 ms |
24668 KB |
Output is correct |
34 |
Correct |
132 ms |
24712 KB |
Output is correct |
35 |
Correct |
135 ms |
24600 KB |
Output is correct |
36 |
Correct |
130 ms |
24656 KB |
Output is correct |
37 |
Correct |
136 ms |
25012 KB |
Output is correct |
38 |
Correct |
126 ms |
24904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
21084 KB |
Output is correct |
2 |
Correct |
7 ms |
21084 KB |
Output is correct |
3 |
Correct |
5 ms |
21332 KB |
Output is correct |
4 |
Correct |
6 ms |
21336 KB |
Output is correct |
5 |
Correct |
5 ms |
21080 KB |
Output is correct |
6 |
Correct |
5 ms |
21340 KB |
Output is correct |
7 |
Correct |
5 ms |
21080 KB |
Output is correct |
8 |
Correct |
5 ms |
21084 KB |
Output is correct |
9 |
Correct |
5 ms |
21116 KB |
Output is correct |
10 |
Correct |
5 ms |
21084 KB |
Output is correct |
11 |
Correct |
5 ms |
21080 KB |
Output is correct |
12 |
Correct |
5 ms |
21084 KB |
Output is correct |
13 |
Correct |
7 ms |
21080 KB |
Output is correct |
14 |
Correct |
7 ms |
21084 KB |
Output is correct |
15 |
Correct |
7 ms |
21084 KB |
Output is correct |
16 |
Correct |
7 ms |
21084 KB |
Output is correct |
17 |
Correct |
6 ms |
21084 KB |
Output is correct |
18 |
Correct |
6 ms |
21084 KB |
Output is correct |
19 |
Correct |
7 ms |
21196 KB |
Output is correct |
20 |
Correct |
7 ms |
21124 KB |
Output is correct |
21 |
Correct |
7 ms |
21084 KB |
Output is correct |
22 |
Correct |
8 ms |
21084 KB |
Output is correct |
23 |
Correct |
684 ms |
56568 KB |
Output is correct |
24 |
Correct |
690 ms |
56532 KB |
Output is correct |
25 |
Correct |
626 ms |
46772 KB |
Output is correct |
26 |
Correct |
671 ms |
55728 KB |
Output is correct |
27 |
Correct |
655 ms |
55600 KB |
Output is correct |
28 |
Correct |
619 ms |
47192 KB |
Output is correct |
29 |
Correct |
606 ms |
47400 KB |
Output is correct |
30 |
Correct |
608 ms |
46640 KB |
Output is correct |
31 |
Correct |
640 ms |
46692 KB |
Output is correct |
32 |
Correct |
725 ms |
46564 KB |
Output is correct |
33 |
Correct |
646 ms |
46520 KB |
Output is correct |
34 |
Correct |
662 ms |
46580 KB |
Output is correct |
35 |
Correct |
616 ms |
46640 KB |
Output is correct |
36 |
Correct |
970 ms |
62332 KB |
Output is correct |
37 |
Correct |
954 ms |
62476 KB |
Output is correct |
38 |
Correct |
1006 ms |
61852 KB |
Output is correct |
39 |
Correct |
933 ms |
61780 KB |
Output is correct |
40 |
Correct |
880 ms |
58432 KB |
Output is correct |
41 |
Correct |
836 ms |
58432 KB |
Output is correct |
42 |
Correct |
702 ms |
57168 KB |
Output is correct |
43 |
Correct |
685 ms |
56912 KB |
Output is correct |
44 |
Correct |
133 ms |
24920 KB |
Output is correct |
45 |
Correct |
135 ms |
24920 KB |
Output is correct |
46 |
Correct |
134 ms |
24924 KB |
Output is correct |
47 |
Correct |
143 ms |
23868 KB |
Output is correct |
48 |
Correct |
127 ms |
23896 KB |
Output is correct |
49 |
Correct |
126 ms |
23976 KB |
Output is correct |
50 |
Correct |
110 ms |
23384 KB |
Output is correct |
51 |
Correct |
97 ms |
23640 KB |
Output is correct |
52 |
Correct |
87 ms |
23752 KB |
Output is correct |
53 |
Correct |
91 ms |
25936 KB |
Output is correct |
54 |
Correct |
158 ms |
24668 KB |
Output is correct |
55 |
Correct |
132 ms |
24712 KB |
Output is correct |
56 |
Correct |
135 ms |
24600 KB |
Output is correct |
57 |
Correct |
130 ms |
24656 KB |
Output is correct |
58 |
Correct |
136 ms |
25012 KB |
Output is correct |
59 |
Correct |
126 ms |
24904 KB |
Output is correct |
60 |
Correct |
1389 ms |
56728 KB |
Output is correct |
61 |
Correct |
1380 ms |
56660 KB |
Output is correct |
62 |
Correct |
1467 ms |
56916 KB |
Output is correct |
63 |
Correct |
1313 ms |
48572 KB |
Output is correct |
64 |
Correct |
1288 ms |
48560 KB |
Output is correct |
65 |
Correct |
1283 ms |
48544 KB |
Output is correct |
66 |
Correct |
742 ms |
46700 KB |
Output is correct |
67 |
Correct |
718 ms |
46688 KB |
Output is correct |
68 |
Correct |
630 ms |
48836 KB |
Output is correct |
69 |
Correct |
611 ms |
62288 KB |
Output is correct |
70 |
Correct |
1403 ms |
55836 KB |
Output is correct |
71 |
Correct |
1358 ms |
56016 KB |
Output is correct |
72 |
Correct |
1252 ms |
55144 KB |
Output is correct |
73 |
Correct |
1287 ms |
55484 KB |
Output is correct |
74 |
Correct |
1335 ms |
55304 KB |
Output is correct |
75 |
Correct |
1307 ms |
55652 KB |
Output is correct |