#include "sequence.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "template/dbgnc.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
struct Tag {
int add = 0;
void apply(const Tag& t) {
add += t.add;
}
};
struct Info {
int mn = 0, mx = 0;
void apply(const Tag& t) {
mn += t.add, mx += t.add;
}
};
Info operator+(const Info& a, const Info& b) {
return {std::min(a.mn, b.mn), std::max(a.mx, b.mx)};
}
struct SegmentTree {
int n;
std::vector<Info> info;
std::vector<Tag> tag;
SegmentTree(int _n) : n(_n), info(4 * n), tag(4 * n) {}
void apply(int k, const Tag& t) {
info[k].apply(t);
tag[k].apply(t);
}
void push(int k) {
apply(k * 2, tag[k]);
apply(k * 2 + 1, tag[k]);
tag[k] = Tag();
}
void update(int k, int l, int r, int ql, int qr, const Tag& t) {
if (l > qr || r < ql) return;
if (ql <= l && r <= qr) {
info[k].apply(t);
tag[k].apply(t);
return;
}
push(k);
int mid = (l + r) / 2;
update(k * 2, l, mid, ql, qr, t);
update(k * 2 + 1, mid + 1, r, ql, qr, t);
info[k] = info[k * 2] + info[k * 2 + 1];
}
Info query(int k, int l, int r, int ql, int qr) {
if (l > qr || r < ql) return {(int) 1e9, (int) -1e9};
if (ql <= l && r <= qr) {
return info[k];
}
push(k);
int mid = (l + r) / 2;
return query(k * 2, l, mid, ql, qr) + query(k * 2 + 1, mid + 1, r, ql, qr);
}
void update(int l, int r, const Tag& t) {
update(1, 0, n - 1, l, r, t);
}
Info query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
};
int sequence(int N, std::vector<int> A) {
std::vector<std::vector<int>> pos(N);
for (int i = 0; i < N; i++) {
pos[--A[i]].push_back(i);
}
SegmentTree tree(N + 1);
for (int i = 0; i < N; i++) {
tree.update(i + 1, N, {1});
}
int ans = 1;
for (int v = 0; v < N; v++) {
for (int i : pos[v]) {
tree.update(i + 1, N, {-2});
}
int sz = pos[v].size();
for (int i = sz - 1; i >= 0; i--) {
int l = pos[v][i];
tree.update(l + 1, N, {2});
while (i + ans < sz) {
int mid = ans + 1;
int r = pos[v][i + mid - 1];
auto rl = tree.query(0, l);
int l1 = rl.mn, r1 = rl.mx;
auto rr = tree.query(r + 1, N);
int l2 = rr.mn - 2 * mid, r2 = rr.mx;
if (std::max(l1, l2) <= std::min(r1, r2)) {
ans++;
} else {
break;
}
}
}
for (int i : pos[v]) {
tree.update(i + 1, N, {-2}); // becomes -1
}
}
return ans;
}
#ifdef LOCAL
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;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
2 ms |
604 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
2 ms |
604 KB |
Output is correct |
22 |
Correct |
2 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
543 ms |
49508 KB |
Output is correct |
3 |
Correct |
530 ms |
52816 KB |
Output is correct |
4 |
Correct |
558 ms |
42716 KB |
Output is correct |
5 |
Correct |
527 ms |
51924 KB |
Output is correct |
6 |
Correct |
529 ms |
51788 KB |
Output is correct |
7 |
Correct |
504 ms |
43432 KB |
Output is correct |
8 |
Correct |
592 ms |
43584 KB |
Output is correct |
9 |
Correct |
562 ms |
42604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
630 ms |
41812 KB |
Output is correct |
3 |
Correct |
660 ms |
42680 KB |
Output is correct |
4 |
Correct |
658 ms |
42684 KB |
Output is correct |
5 |
Correct |
675 ms |
42784 KB |
Output is correct |
6 |
Correct |
649 ms |
42940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
631 ms |
55236 KB |
Output is correct |
2 |
Correct |
619 ms |
58648 KB |
Output is correct |
3 |
Correct |
626 ms |
58196 KB |
Output is correct |
4 |
Correct |
644 ms |
57932 KB |
Output is correct |
5 |
Correct |
626 ms |
54524 KB |
Output is correct |
6 |
Correct |
623 ms |
54516 KB |
Output is correct |
7 |
Correct |
600 ms |
53344 KB |
Output is correct |
8 |
Correct |
548 ms |
53076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
2 ms |
604 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
2 ms |
604 KB |
Output is correct |
22 |
Correct |
2 ms |
604 KB |
Output is correct |
23 |
Correct |
83 ms |
8288 KB |
Output is correct |
24 |
Correct |
85 ms |
8288 KB |
Output is correct |
25 |
Correct |
84 ms |
8280 KB |
Output is correct |
26 |
Correct |
89 ms |
7356 KB |
Output is correct |
27 |
Correct |
87 ms |
7356 KB |
Output is correct |
28 |
Correct |
87 ms |
7360 KB |
Output is correct |
29 |
Correct |
85 ms |
7000 KB |
Output is correct |
30 |
Correct |
102 ms |
7156 KB |
Output is correct |
31 |
Correct |
97 ms |
7120 KB |
Output is correct |
32 |
Correct |
83 ms |
9196 KB |
Output is correct |
33 |
Correct |
84 ms |
7928 KB |
Output is correct |
34 |
Correct |
89 ms |
8108 KB |
Output is correct |
35 |
Correct |
91 ms |
8032 KB |
Output is correct |
36 |
Correct |
87 ms |
8024 KB |
Output is correct |
37 |
Correct |
86 ms |
7992 KB |
Output is correct |
38 |
Correct |
89 ms |
8108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
2 ms |
604 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
2 ms |
604 KB |
Output is correct |
22 |
Correct |
2 ms |
604 KB |
Output is correct |
23 |
Correct |
543 ms |
49508 KB |
Output is correct |
24 |
Correct |
530 ms |
52816 KB |
Output is correct |
25 |
Correct |
558 ms |
42716 KB |
Output is correct |
26 |
Correct |
527 ms |
51924 KB |
Output is correct |
27 |
Correct |
529 ms |
51788 KB |
Output is correct |
28 |
Correct |
504 ms |
43432 KB |
Output is correct |
29 |
Correct |
592 ms |
43584 KB |
Output is correct |
30 |
Correct |
562 ms |
42604 KB |
Output is correct |
31 |
Correct |
630 ms |
41812 KB |
Output is correct |
32 |
Correct |
660 ms |
42680 KB |
Output is correct |
33 |
Correct |
658 ms |
42684 KB |
Output is correct |
34 |
Correct |
675 ms |
42784 KB |
Output is correct |
35 |
Correct |
649 ms |
42940 KB |
Output is correct |
36 |
Correct |
631 ms |
55236 KB |
Output is correct |
37 |
Correct |
619 ms |
58648 KB |
Output is correct |
38 |
Correct |
626 ms |
58196 KB |
Output is correct |
39 |
Correct |
644 ms |
57932 KB |
Output is correct |
40 |
Correct |
626 ms |
54524 KB |
Output is correct |
41 |
Correct |
623 ms |
54516 KB |
Output is correct |
42 |
Correct |
600 ms |
53344 KB |
Output is correct |
43 |
Correct |
548 ms |
53076 KB |
Output is correct |
44 |
Correct |
83 ms |
8288 KB |
Output is correct |
45 |
Correct |
85 ms |
8288 KB |
Output is correct |
46 |
Correct |
84 ms |
8280 KB |
Output is correct |
47 |
Correct |
89 ms |
7356 KB |
Output is correct |
48 |
Correct |
87 ms |
7356 KB |
Output is correct |
49 |
Correct |
87 ms |
7360 KB |
Output is correct |
50 |
Correct |
85 ms |
7000 KB |
Output is correct |
51 |
Correct |
102 ms |
7156 KB |
Output is correct |
52 |
Correct |
97 ms |
7120 KB |
Output is correct |
53 |
Correct |
83 ms |
9196 KB |
Output is correct |
54 |
Correct |
84 ms |
7928 KB |
Output is correct |
55 |
Correct |
89 ms |
8108 KB |
Output is correct |
56 |
Correct |
91 ms |
8032 KB |
Output is correct |
57 |
Correct |
87 ms |
8024 KB |
Output is correct |
58 |
Correct |
86 ms |
7992 KB |
Output is correct |
59 |
Correct |
89 ms |
8108 KB |
Output is correct |
60 |
Correct |
691 ms |
53068 KB |
Output is correct |
61 |
Correct |
697 ms |
52808 KB |
Output is correct |
62 |
Correct |
693 ms |
52828 KB |
Output is correct |
63 |
Correct |
677 ms |
44664 KB |
Output is correct |
64 |
Correct |
651 ms |
44632 KB |
Output is correct |
65 |
Correct |
670 ms |
44640 KB |
Output is correct |
66 |
Correct |
619 ms |
42796 KB |
Output is correct |
67 |
Correct |
603 ms |
42928 KB |
Output is correct |
68 |
Correct |
699 ms |
45088 KB |
Output is correct |
69 |
Correct |
510 ms |
58316 KB |
Output is correct |
70 |
Correct |
687 ms |
51900 KB |
Output is correct |
71 |
Correct |
710 ms |
51720 KB |
Output is correct |
72 |
Correct |
731 ms |
51240 KB |
Output is correct |
73 |
Correct |
689 ms |
51580 KB |
Output is correct |
74 |
Correct |
710 ms |
51220 KB |
Output is correct |
75 |
Correct |
697 ms |
51572 KB |
Output is correct |