#include <bits/stdc++.h>
#include "sequence.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
#define md ((l + r) >> 1)
const int N = 500'005, inf = 1e9;
struct node {
int mn, mx, lazy;
node() {
mn = inf;
mx = -inf;
lazy = 0;
}
friend node operator+(const node &l, const node &r) {
node ret;
ret.mn = min(l.mn, r.mn);
ret.mx = max(l.mx, r.mx);
return ret;
}
};
struct segtree {
node seg[1 << 20];
void build(int i, int l, int r) {
if (l == r) {
seg[i].mn = seg[i].mx = 0;
return;
}
build(i << 1, l, md);
build(i << 1 | 1, md + 1, r);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
void process(int i, int l, int r) {
if (l != r) {
for (auto c : {i << 1, i << 1 | 1}) {
seg[c].lazy += seg[i].lazy;
}
}
seg[i].mn += seg[i].lazy;
seg[i].mx += seg[i].lazy;
seg[i].lazy = 0;
}
void add(int i, int l, int r, int s, int e, int v) {
process(i, l, r);
if (s <= l && r <= e) {
seg[i].lazy += v;
process(i, l, r);
return;
}
if (r < s || e < l) {
return;
}
add(i << 1, l, md, s, e, v);
add(i << 1 | 1, md + 1, r, s, e, v);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
node get(int i, int l, int r, int s, int e) {
process(i, l, r);
if (s <= l && r <= e) {
return seg[i];
}
if (r < s || e < l) {
return node();
}
return get(i << 1, l, md, s, e) + get(i << 1 | 1, md + 1, r, s, e);
}
} suf;
struct BIT {
int n, bit[N];
void init(int _n) {
n = _n;
for (int i = 0; i < n; i++) {
bit[i] = inf;
}
}
void upd(int x, int v) {
for (int i = x; i < n; i |= i + 1) {
bit[i] = min(bit[i], v);
}
}
int get(int r) {
if (r < 0) return inf;
int mn = 1e9;
for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
mn = min(mn, bit[i]);
}
return mn;
}
} bit;
int sequence(int n, vector<int> a) {
vector<int> gud[n + 1];
for (int i = 0; i <= n; i++) {
gud[i].push_back(-1);
}
for (int i = 0; i < n; i++) {
gud[a[i]].push_back(i);
}
for (int i = 0; i <= n; i++) {
gud[i].push_back(n);
}
suf.build(1, 0, n);
for (int i = 0; i < n; i++) {
suf.add(1, 0, n, 0, i, 1);
}
int mx = 0;
for (int i = 0; i <= n; i++) {
if (SZ(gud[i]) == 2) continue;
int ans[SZ(gud[i])];
for (int j = 0; j < SZ(gud[i]); j++) {
ans[j] = j;
}
for (auto x : gud[i]) {
suf.add(1, 0, n, 0, x, -1);
}
array<int, 2> vl[SZ(gud[i])], vr[SZ(gud[i])];
for (int j = 1; j < SZ(gud[i]) - 1; j++) {
vl[j] = {inf, -inf};
node val = suf.get(1, 0, n, gud[i][j - 1] + 1, gud[i][j]);
vl[j][0] = val.mn;
vl[j][1] = val.mx;
}
for (int r = SZ(gud[i]) - 2; r >= 1; r--) {
vr[r] = {inf, -inf};
node val = suf.get(1, 0, n, gud[i][r] + 1, gud[i][r + 1]);
vr[r][0] = val.mn;
vr[r][1] = val.mx;
}
vector<array<int, 3>> v;
for (int j = 1; j < SZ(gud[i]) - 1; j++) {
v.push_back({vl[j][0], vl[j][1], j});
}
sort(v.begin(), v.end());
vector<int> ask[SZ(v) + 1];
for (int r = 1; r < SZ(gud[i]) - 1; r++) {
int pos = lower_bound(v.begin(), v.end(), (array<int, 3>) {vr[r][0], 0, 0}) - v.begin();
ask[pos].push_back(r);
}
vector<int> vals;
for (int l = 1; l < SZ(gud[i]) - 1; l++) {
vals.push_back(vl[l][0] + l);
}
sort(vals.begin(), vals.end());
vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
bit.init(SZ(vals) + 5);
for (int i = SZ(v); i >= 0; i--) {
if (i < SZ(v)) {
int x = v[i][0] + v[i][2];
int pos = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
bit.upd(pos, v[i][2]);
}
for (auto r : ask[i]) {
int x = r + vr[r][1] + 1;
int pos = lower_bound(vals.begin(), vals.end(), x + 1) - vals.begin() - 1;
ans[r] = min(ans[r], bit.get(pos));
}
}
vals.clear();
for (int l = 1; l < SZ(gud[i]) - 1; l++) {
vals.push_back(l - vl[l][1]);
}
sort(vals.begin(), vals.end());
vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
bit.init(SZ(vals) + 5);
for (int i = 0; i <= SZ(v); i++) {
for (auto r : ask[i]) {
int x = r - vr[r][0] + 1;
int pos = lower_bound(vals.begin(), vals.end(), x + 1) - vals.begin() - 1;
ans[r] = min(ans[r], bit.get(pos));
}
if (i < SZ(v)) {
int x = v[i][2] - v[i][1];
int pos = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
bit.upd(pos, v[i][2]);
}
}
// for (int l = 1; l <= r; l++) {
// if (vr[0] <= vl[l][0]) {
// if (vl[l][0] + l <= r + vr[1] + 1) {
// ans = max(ans, r - l + 1);
// break;
// }
// } else {
// //vr[0] >= vl[l][0]
// if (l - vl[l][1] <= r - vr[0] + 1) {
// ans = max(ans, r - l + 1);
// }
// }
// }
for (int j = 0; j < SZ(gud[i]); j++) {
mx = max(mx, j - ans[j] + 1);
}
for (auto x : gud[i]) {
suf.add(1, 0, n, 0, x, -1);
}
}
return mx;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14424 KB |
Output is correct |
2 |
Correct |
3 ms |
14428 KB |
Output is correct |
3 |
Correct |
3 ms |
14428 KB |
Output is correct |
4 |
Correct |
3 ms |
14428 KB |
Output is correct |
5 |
Correct |
3 ms |
14428 KB |
Output is correct |
6 |
Correct |
3 ms |
14428 KB |
Output is correct |
7 |
Correct |
3 ms |
14428 KB |
Output is correct |
8 |
Correct |
3 ms |
14428 KB |
Output is correct |
9 |
Correct |
3 ms |
14428 KB |
Output is correct |
10 |
Correct |
3 ms |
14400 KB |
Output is correct |
11 |
Correct |
4 ms |
14428 KB |
Output is correct |
12 |
Correct |
5 ms |
14428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14424 KB |
Output is correct |
2 |
Correct |
3 ms |
14428 KB |
Output is correct |
3 |
Correct |
3 ms |
14428 KB |
Output is correct |
4 |
Correct |
3 ms |
14428 KB |
Output is correct |
5 |
Correct |
3 ms |
14428 KB |
Output is correct |
6 |
Correct |
3 ms |
14428 KB |
Output is correct |
7 |
Correct |
3 ms |
14428 KB |
Output is correct |
8 |
Correct |
3 ms |
14428 KB |
Output is correct |
9 |
Correct |
3 ms |
14428 KB |
Output is correct |
10 |
Correct |
3 ms |
14400 KB |
Output is correct |
11 |
Correct |
4 ms |
14428 KB |
Output is correct |
12 |
Correct |
5 ms |
14428 KB |
Output is correct |
13 |
Correct |
6 ms |
14428 KB |
Output is correct |
14 |
Correct |
6 ms |
14428 KB |
Output is correct |
15 |
Correct |
7 ms |
14684 KB |
Output is correct |
16 |
Correct |
6 ms |
14688 KB |
Output is correct |
17 |
Correct |
6 ms |
14684 KB |
Output is correct |
18 |
Correct |
6 ms |
14428 KB |
Output is correct |
19 |
Correct |
6 ms |
14684 KB |
Output is correct |
20 |
Correct |
6 ms |
14680 KB |
Output is correct |
21 |
Correct |
6 ms |
14684 KB |
Output is correct |
22 |
Correct |
6 ms |
14680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14424 KB |
Output is correct |
2 |
Correct |
831 ms |
47444 KB |
Output is correct |
3 |
Correct |
865 ms |
47464 KB |
Output is correct |
4 |
Correct |
905 ms |
55320 KB |
Output is correct |
5 |
Correct |
870 ms |
47952 KB |
Output is correct |
6 |
Correct |
828 ms |
47940 KB |
Output is correct |
7 |
Correct |
832 ms |
49140 KB |
Output is correct |
8 |
Correct |
846 ms |
49172 KB |
Output is correct |
9 |
Correct |
931 ms |
61032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14428 KB |
Output is correct |
2 |
Correct |
981 ms |
72136 KB |
Output is correct |
3 |
Correct |
987 ms |
62400 KB |
Output is correct |
4 |
Correct |
1004 ms |
62644 KB |
Output is correct |
5 |
Correct |
1038 ms |
70992 KB |
Output is correct |
6 |
Correct |
884 ms |
71476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1207 ms |
45840 KB |
Output is correct |
2 |
Correct |
1047 ms |
45848 KB |
Output is correct |
3 |
Correct |
1048 ms |
45848 KB |
Output is correct |
4 |
Correct |
1067 ms |
45844 KB |
Output is correct |
5 |
Correct |
939 ms |
45848 KB |
Output is correct |
6 |
Correct |
1002 ms |
45848 KB |
Output is correct |
7 |
Correct |
857 ms |
45904 KB |
Output is correct |
8 |
Correct |
882 ms |
45928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14424 KB |
Output is correct |
2 |
Correct |
3 ms |
14428 KB |
Output is correct |
3 |
Correct |
3 ms |
14428 KB |
Output is correct |
4 |
Correct |
3 ms |
14428 KB |
Output is correct |
5 |
Correct |
3 ms |
14428 KB |
Output is correct |
6 |
Correct |
3 ms |
14428 KB |
Output is correct |
7 |
Correct |
3 ms |
14428 KB |
Output is correct |
8 |
Correct |
3 ms |
14428 KB |
Output is correct |
9 |
Correct |
3 ms |
14428 KB |
Output is correct |
10 |
Correct |
3 ms |
14400 KB |
Output is correct |
11 |
Correct |
4 ms |
14428 KB |
Output is correct |
12 |
Correct |
5 ms |
14428 KB |
Output is correct |
13 |
Correct |
6 ms |
14428 KB |
Output is correct |
14 |
Correct |
6 ms |
14428 KB |
Output is correct |
15 |
Correct |
7 ms |
14684 KB |
Output is correct |
16 |
Correct |
6 ms |
14688 KB |
Output is correct |
17 |
Correct |
6 ms |
14684 KB |
Output is correct |
18 |
Correct |
6 ms |
14428 KB |
Output is correct |
19 |
Correct |
6 ms |
14684 KB |
Output is correct |
20 |
Correct |
6 ms |
14680 KB |
Output is correct |
21 |
Correct |
6 ms |
14684 KB |
Output is correct |
22 |
Correct |
6 ms |
14680 KB |
Output is correct |
23 |
Correct |
145 ms |
19800 KB |
Output is correct |
24 |
Correct |
142 ms |
20296 KB |
Output is correct |
25 |
Correct |
142 ms |
20056 KB |
Output is correct |
26 |
Correct |
162 ms |
20504 KB |
Output is correct |
27 |
Correct |
152 ms |
20412 KB |
Output is correct |
28 |
Correct |
150 ms |
20492 KB |
Output is correct |
29 |
Correct |
138 ms |
21380 KB |
Output is correct |
30 |
Correct |
138 ms |
21468 KB |
Output is correct |
31 |
Correct |
131 ms |
26024 KB |
Output is correct |
32 |
Correct |
118 ms |
20008 KB |
Output is correct |
33 |
Correct |
150 ms |
20800 KB |
Output is correct |
34 |
Correct |
145 ms |
20752 KB |
Output is correct |
35 |
Correct |
160 ms |
21052 KB |
Output is correct |
36 |
Correct |
148 ms |
21296 KB |
Output is correct |
37 |
Correct |
143 ms |
21016 KB |
Output is correct |
38 |
Correct |
143 ms |
21012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14424 KB |
Output is correct |
2 |
Correct |
3 ms |
14428 KB |
Output is correct |
3 |
Correct |
3 ms |
14428 KB |
Output is correct |
4 |
Correct |
3 ms |
14428 KB |
Output is correct |
5 |
Correct |
3 ms |
14428 KB |
Output is correct |
6 |
Correct |
3 ms |
14428 KB |
Output is correct |
7 |
Correct |
3 ms |
14428 KB |
Output is correct |
8 |
Correct |
3 ms |
14428 KB |
Output is correct |
9 |
Correct |
3 ms |
14428 KB |
Output is correct |
10 |
Correct |
3 ms |
14400 KB |
Output is correct |
11 |
Correct |
4 ms |
14428 KB |
Output is correct |
12 |
Correct |
5 ms |
14428 KB |
Output is correct |
13 |
Correct |
6 ms |
14428 KB |
Output is correct |
14 |
Correct |
6 ms |
14428 KB |
Output is correct |
15 |
Correct |
7 ms |
14684 KB |
Output is correct |
16 |
Correct |
6 ms |
14688 KB |
Output is correct |
17 |
Correct |
6 ms |
14684 KB |
Output is correct |
18 |
Correct |
6 ms |
14428 KB |
Output is correct |
19 |
Correct |
6 ms |
14684 KB |
Output is correct |
20 |
Correct |
6 ms |
14680 KB |
Output is correct |
21 |
Correct |
6 ms |
14684 KB |
Output is correct |
22 |
Correct |
6 ms |
14680 KB |
Output is correct |
23 |
Correct |
831 ms |
47444 KB |
Output is correct |
24 |
Correct |
865 ms |
47464 KB |
Output is correct |
25 |
Correct |
905 ms |
55320 KB |
Output is correct |
26 |
Correct |
870 ms |
47952 KB |
Output is correct |
27 |
Correct |
828 ms |
47940 KB |
Output is correct |
28 |
Correct |
832 ms |
49140 KB |
Output is correct |
29 |
Correct |
846 ms |
49172 KB |
Output is correct |
30 |
Correct |
931 ms |
61032 KB |
Output is correct |
31 |
Correct |
981 ms |
72136 KB |
Output is correct |
32 |
Correct |
987 ms |
62400 KB |
Output is correct |
33 |
Correct |
1004 ms |
62644 KB |
Output is correct |
34 |
Correct |
1038 ms |
70992 KB |
Output is correct |
35 |
Correct |
884 ms |
71476 KB |
Output is correct |
36 |
Correct |
1207 ms |
45840 KB |
Output is correct |
37 |
Correct |
1047 ms |
45848 KB |
Output is correct |
38 |
Correct |
1048 ms |
45848 KB |
Output is correct |
39 |
Correct |
1067 ms |
45844 KB |
Output is correct |
40 |
Correct |
939 ms |
45848 KB |
Output is correct |
41 |
Correct |
1002 ms |
45848 KB |
Output is correct |
42 |
Correct |
857 ms |
45904 KB |
Output is correct |
43 |
Correct |
882 ms |
45928 KB |
Output is correct |
44 |
Correct |
145 ms |
19800 KB |
Output is correct |
45 |
Correct |
142 ms |
20296 KB |
Output is correct |
46 |
Correct |
142 ms |
20056 KB |
Output is correct |
47 |
Correct |
162 ms |
20504 KB |
Output is correct |
48 |
Correct |
152 ms |
20412 KB |
Output is correct |
49 |
Correct |
150 ms |
20492 KB |
Output is correct |
50 |
Correct |
138 ms |
21380 KB |
Output is correct |
51 |
Correct |
138 ms |
21468 KB |
Output is correct |
52 |
Correct |
131 ms |
26024 KB |
Output is correct |
53 |
Correct |
118 ms |
20008 KB |
Output is correct |
54 |
Correct |
150 ms |
20800 KB |
Output is correct |
55 |
Correct |
145 ms |
20752 KB |
Output is correct |
56 |
Correct |
160 ms |
21052 KB |
Output is correct |
57 |
Correct |
148 ms |
21296 KB |
Output is correct |
58 |
Correct |
143 ms |
21016 KB |
Output is correct |
59 |
Correct |
143 ms |
21012 KB |
Output is correct |
60 |
Correct |
1146 ms |
50660 KB |
Output is correct |
61 |
Correct |
1142 ms |
50420 KB |
Output is correct |
62 |
Correct |
1189 ms |
50512 KB |
Output is correct |
63 |
Correct |
1114 ms |
51068 KB |
Output is correct |
64 |
Correct |
1113 ms |
50768 KB |
Output is correct |
65 |
Correct |
1068 ms |
50864 KB |
Output is correct |
66 |
Correct |
1024 ms |
57988 KB |
Output is correct |
67 |
Correct |
966 ms |
57916 KB |
Output is correct |
68 |
Correct |
880 ms |
84288 KB |
Output is correct |
69 |
Correct |
798 ms |
48468 KB |
Output is correct |
70 |
Correct |
1139 ms |
54264 KB |
Output is correct |
71 |
Correct |
1159 ms |
55104 KB |
Output is correct |
72 |
Correct |
1116 ms |
56324 KB |
Output is correct |
73 |
Correct |
1114 ms |
56012 KB |
Output is correct |
74 |
Correct |
1124 ms |
57676 KB |
Output is correct |
75 |
Correct |
1142 ms |
55676 KB |
Output is correct |