# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
894261 |
2023-12-28T03:09:02 Z |
box |
Sequence (APIO23_sequence) |
C++17 |
|
1912 ms |
76848 KB |
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 5e5, N_ = 1 << 19;
namespace D1 {
struct node {
int minL, minR, maxL, maxR, sum;
};
node operator+(const node &u, const node &v) {
return {min(u.minL, u.sum + v.minL), min(v.minR, v.sum + u.minR),
max(u.maxL, u.sum + v.maxL), max(v.maxR, v.sum + u.maxR),
u.sum + v.sum};
}
const node id = {0, 0, 0, 0, 0};
node st[N_ * 2];
int n_;
void activate(int i) {
st[i += n_] = {-1, -1, 0, 0, -1};
while (i /= 2) st[i] = st[i * 2] + st[i * 2 + 1];
}
node qry(int l, int r) {
node u = id, v = id;
for (l += n_, r += n_; l <= r; l /= 2, r /= 2) {
if (l & 1) u = u + st[l++];
if (~r & 1) v = st[r--] + v;
}
return u + v;
}
} // namespace D1
const int M_ = 1 << 20, offset = N_, INF = 1e8;
int mx[M_ * 2];
vi reset;
void upd(int i, int x) {
reset.push_back(i);
i += offset;
i += M_;
while (i) mx[i] = max(mx[i], x), i /= 2;
}
int qry(int l, int r) {
l += offset;
r += offset;
int x = -INF;
for (l += M_, r += M_; l <= r; l /= 2, r /= 2) {
if (l & 1) x = max(x, mx[l++]);
if (~r & 1) x = max(x, mx[r--]);
}
return x;
}
void clr() {
for (int i : reset) {
i += offset;
i += M_;
while (i) mx[i] = -INF, i /= 2;
}
vi().swap(reset);
}
int minL[N], maxL[N], minR[N], maxR[N], sumL[N], sumR[N], ans;
void dnc(int l, int r) {
if (l < r) {
int m = (l + r) / 2;
dnc(l, m);
dnc(m + 1, r);
int sum = 0;
vector<array<int, 3>> left, right;
for (int i = m; i >= l; i--) {
if (i < m) sum += sumR[i];
int v = maxL[i] + sum + (m - i + 1);
int u = minL[i] + sum - (m - i + 1) + 1;
v *= -1;
left.push_back({v, u, (m - i + 1)});
}
sum = 0;
for (int i = m + 1; i <= r; i++) {
sum += sumL[i];
int v = maxR[i] + sum + (i - m);
int u = minR[i] + sum - (i - m);
u *= -1;
right.push_back({v, u, i - m});
}
sort(left.begin(), left.end());
sort(right.begin(), right.end());
int p = 0;
for (auto [u, v, k] : right) {
while (p < int(left.size()) && left[p][0] <= u) {
upd(left[p][1], left[p][2]);
p++;
}
ans = max(ans, k + qry(-offset, v));
}
clr();
}
}
void solve(int n, vi a) {
vector<vi> ii(n);
for (int i = 0; i < n; i++) ii[a[i]].push_back(i);
D1::n_ = 1;
while (D1::n_ < n) D1::n_ *= 2;
for (int i = 0; i < n; i++) D1::st[D1::n_ + i] = {0, 0, 1, 1, 1};
for (int i = D1::n_ - 1; i > 0; i--)
D1::st[i] = D1::st[i * 2] + D1::st[i * 2 + 1];
for (int x = 0; x < n; x++) {
if (ii[x].empty()) continue;
int m = ii[x].size();
for (int p = 0; p < m; p++) {
D1::node u = D1::qry(p == 0 ? 0 : ii[x][p - 1] + 1, ii[x][p] - 1);
D1::node v = D1::qry(ii[x][p] + 1, p == m - 1 ? n - 1 : ii[x][p + 1] - 1);
sumL[p] = u.sum;
sumR[p] = v.sum;
minL[p] = u.minR;
maxL[p] = u.maxR;
minR[p] = v.minL;
maxR[p] = v.maxL;
}
dnc(0, m - 1);
for (int i : ii[x]) {
D1::activate(i);
}
}
}
int sequence(int n, vi a) {
for (int i = 0; i < M_ * 2; i++) mx[i] = -INF;
for (int i = 0; i < n; i++) a[i]--;
ans = 1;
solve(n, a);
for (int i = 0; i < n; i++) a[i] = n - a[i] - 1;
solve(n, a);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
20828 KB |
Output is correct |
2 |
Correct |
3 ms |
20928 KB |
Output is correct |
3 |
Correct |
3 ms |
20828 KB |
Output is correct |
4 |
Correct |
3 ms |
20824 KB |
Output is correct |
5 |
Correct |
3 ms |
20828 KB |
Output is correct |
6 |
Correct |
3 ms |
20888 KB |
Output is correct |
7 |
Correct |
3 ms |
20824 KB |
Output is correct |
8 |
Correct |
3 ms |
20928 KB |
Output is correct |
9 |
Correct |
3 ms |
20828 KB |
Output is correct |
10 |
Correct |
3 ms |
20828 KB |
Output is correct |
11 |
Correct |
3 ms |
20828 KB |
Output is correct |
12 |
Correct |
3 ms |
20828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
20828 KB |
Output is correct |
2 |
Correct |
3 ms |
20928 KB |
Output is correct |
3 |
Correct |
3 ms |
20828 KB |
Output is correct |
4 |
Correct |
3 ms |
20824 KB |
Output is correct |
5 |
Correct |
3 ms |
20828 KB |
Output is correct |
6 |
Correct |
3 ms |
20888 KB |
Output is correct |
7 |
Correct |
3 ms |
20824 KB |
Output is correct |
8 |
Correct |
3 ms |
20928 KB |
Output is correct |
9 |
Correct |
3 ms |
20828 KB |
Output is correct |
10 |
Correct |
3 ms |
20828 KB |
Output is correct |
11 |
Correct |
3 ms |
20828 KB |
Output is correct |
12 |
Correct |
3 ms |
20828 KB |
Output is correct |
13 |
Correct |
4 ms |
21084 KB |
Output is correct |
14 |
Correct |
5 ms |
20828 KB |
Output is correct |
15 |
Correct |
6 ms |
20828 KB |
Output is correct |
16 |
Correct |
7 ms |
20828 KB |
Output is correct |
17 |
Correct |
6 ms |
20828 KB |
Output is correct |
18 |
Correct |
4 ms |
21100 KB |
Output is correct |
19 |
Correct |
5 ms |
21084 KB |
Output is correct |
20 |
Correct |
6 ms |
20940 KB |
Output is correct |
21 |
Correct |
6 ms |
21084 KB |
Output is correct |
22 |
Correct |
6 ms |
21080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
20828 KB |
Output is correct |
2 |
Correct |
549 ms |
71124 KB |
Output is correct |
3 |
Correct |
540 ms |
71116 KB |
Output is correct |
4 |
Correct |
1551 ms |
63088 KB |
Output is correct |
5 |
Correct |
538 ms |
70080 KB |
Output is correct |
6 |
Correct |
513 ms |
70092 KB |
Output is correct |
7 |
Correct |
1215 ms |
61952 KB |
Output is correct |
8 |
Correct |
1170 ms |
62248 KB |
Output is correct |
9 |
Correct |
1610 ms |
64904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
20928 KB |
Output is correct |
2 |
Correct |
1787 ms |
68672 KB |
Output is correct |
3 |
Correct |
1715 ms |
64884 KB |
Output is correct |
4 |
Correct |
1775 ms |
65136 KB |
Output is correct |
5 |
Correct |
1912 ms |
69980 KB |
Output is correct |
6 |
Correct |
1675 ms |
66076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
824 ms |
76848 KB |
Output is correct |
2 |
Correct |
839 ms |
76828 KB |
Output is correct |
3 |
Correct |
767 ms |
76240 KB |
Output is correct |
4 |
Correct |
748 ms |
76240 KB |
Output is correct |
5 |
Correct |
659 ms |
72828 KB |
Output is correct |
6 |
Correct |
662 ms |
72960 KB |
Output is correct |
7 |
Correct |
545 ms |
71660 KB |
Output is correct |
8 |
Correct |
563 ms |
71272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
20828 KB |
Output is correct |
2 |
Correct |
3 ms |
20928 KB |
Output is correct |
3 |
Correct |
3 ms |
20828 KB |
Output is correct |
4 |
Correct |
3 ms |
20824 KB |
Output is correct |
5 |
Correct |
3 ms |
20828 KB |
Output is correct |
6 |
Correct |
3 ms |
20888 KB |
Output is correct |
7 |
Correct |
3 ms |
20824 KB |
Output is correct |
8 |
Correct |
3 ms |
20928 KB |
Output is correct |
9 |
Correct |
3 ms |
20828 KB |
Output is correct |
10 |
Correct |
3 ms |
20828 KB |
Output is correct |
11 |
Correct |
3 ms |
20828 KB |
Output is correct |
12 |
Correct |
3 ms |
20828 KB |
Output is correct |
13 |
Correct |
4 ms |
21084 KB |
Output is correct |
14 |
Correct |
5 ms |
20828 KB |
Output is correct |
15 |
Correct |
6 ms |
20828 KB |
Output is correct |
16 |
Correct |
7 ms |
20828 KB |
Output is correct |
17 |
Correct |
6 ms |
20828 KB |
Output is correct |
18 |
Correct |
4 ms |
21100 KB |
Output is correct |
19 |
Correct |
5 ms |
21084 KB |
Output is correct |
20 |
Correct |
6 ms |
20940 KB |
Output is correct |
21 |
Correct |
6 ms |
21084 KB |
Output is correct |
22 |
Correct |
6 ms |
21080 KB |
Output is correct |
23 |
Correct |
107 ms |
29872 KB |
Output is correct |
24 |
Correct |
123 ms |
29892 KB |
Output is correct |
25 |
Correct |
125 ms |
29888 KB |
Output is correct |
26 |
Correct |
175 ms |
28788 KB |
Output is correct |
27 |
Correct |
170 ms |
28824 KB |
Output is correct |
28 |
Correct |
168 ms |
28848 KB |
Output is correct |
29 |
Correct |
222 ms |
28668 KB |
Output is correct |
30 |
Correct |
228 ms |
28760 KB |
Output is correct |
31 |
Correct |
252 ms |
30692 KB |
Output is correct |
32 |
Correct |
86 ms |
31064 KB |
Output is correct |
33 |
Correct |
140 ms |
29792 KB |
Output is correct |
34 |
Correct |
147 ms |
30028 KB |
Output is correct |
35 |
Correct |
153 ms |
29880 KB |
Output is correct |
36 |
Correct |
156 ms |
30000 KB |
Output is correct |
37 |
Correct |
144 ms |
30012 KB |
Output is correct |
38 |
Correct |
133 ms |
30028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
20828 KB |
Output is correct |
2 |
Correct |
3 ms |
20928 KB |
Output is correct |
3 |
Correct |
3 ms |
20828 KB |
Output is correct |
4 |
Correct |
3 ms |
20824 KB |
Output is correct |
5 |
Correct |
3 ms |
20828 KB |
Output is correct |
6 |
Correct |
3 ms |
20888 KB |
Output is correct |
7 |
Correct |
3 ms |
20824 KB |
Output is correct |
8 |
Correct |
3 ms |
20928 KB |
Output is correct |
9 |
Correct |
3 ms |
20828 KB |
Output is correct |
10 |
Correct |
3 ms |
20828 KB |
Output is correct |
11 |
Correct |
3 ms |
20828 KB |
Output is correct |
12 |
Correct |
3 ms |
20828 KB |
Output is correct |
13 |
Correct |
4 ms |
21084 KB |
Output is correct |
14 |
Correct |
5 ms |
20828 KB |
Output is correct |
15 |
Correct |
6 ms |
20828 KB |
Output is correct |
16 |
Correct |
7 ms |
20828 KB |
Output is correct |
17 |
Correct |
6 ms |
20828 KB |
Output is correct |
18 |
Correct |
4 ms |
21100 KB |
Output is correct |
19 |
Correct |
5 ms |
21084 KB |
Output is correct |
20 |
Correct |
6 ms |
20940 KB |
Output is correct |
21 |
Correct |
6 ms |
21084 KB |
Output is correct |
22 |
Correct |
6 ms |
21080 KB |
Output is correct |
23 |
Correct |
549 ms |
71124 KB |
Output is correct |
24 |
Correct |
540 ms |
71116 KB |
Output is correct |
25 |
Correct |
1551 ms |
63088 KB |
Output is correct |
26 |
Correct |
538 ms |
70080 KB |
Output is correct |
27 |
Correct |
513 ms |
70092 KB |
Output is correct |
28 |
Correct |
1215 ms |
61952 KB |
Output is correct |
29 |
Correct |
1170 ms |
62248 KB |
Output is correct |
30 |
Correct |
1610 ms |
64904 KB |
Output is correct |
31 |
Correct |
1787 ms |
68672 KB |
Output is correct |
32 |
Correct |
1715 ms |
64884 KB |
Output is correct |
33 |
Correct |
1775 ms |
65136 KB |
Output is correct |
34 |
Correct |
1912 ms |
69980 KB |
Output is correct |
35 |
Correct |
1675 ms |
66076 KB |
Output is correct |
36 |
Correct |
824 ms |
76848 KB |
Output is correct |
37 |
Correct |
839 ms |
76828 KB |
Output is correct |
38 |
Correct |
767 ms |
76240 KB |
Output is correct |
39 |
Correct |
748 ms |
76240 KB |
Output is correct |
40 |
Correct |
659 ms |
72828 KB |
Output is correct |
41 |
Correct |
662 ms |
72960 KB |
Output is correct |
42 |
Correct |
545 ms |
71660 KB |
Output is correct |
43 |
Correct |
563 ms |
71272 KB |
Output is correct |
44 |
Correct |
107 ms |
29872 KB |
Output is correct |
45 |
Correct |
123 ms |
29892 KB |
Output is correct |
46 |
Correct |
125 ms |
29888 KB |
Output is correct |
47 |
Correct |
175 ms |
28788 KB |
Output is correct |
48 |
Correct |
170 ms |
28824 KB |
Output is correct |
49 |
Correct |
168 ms |
28848 KB |
Output is correct |
50 |
Correct |
222 ms |
28668 KB |
Output is correct |
51 |
Correct |
228 ms |
28760 KB |
Output is correct |
52 |
Correct |
252 ms |
30692 KB |
Output is correct |
53 |
Correct |
86 ms |
31064 KB |
Output is correct |
54 |
Correct |
140 ms |
29792 KB |
Output is correct |
55 |
Correct |
147 ms |
30028 KB |
Output is correct |
56 |
Correct |
153 ms |
29880 KB |
Output is correct |
57 |
Correct |
156 ms |
30000 KB |
Output is correct |
58 |
Correct |
144 ms |
30012 KB |
Output is correct |
59 |
Correct |
133 ms |
30028 KB |
Output is correct |
60 |
Correct |
1000 ms |
71120 KB |
Output is correct |
61 |
Correct |
997 ms |
71108 KB |
Output is correct |
62 |
Correct |
954 ms |
71128 KB |
Output is correct |
63 |
Correct |
1417 ms |
63000 KB |
Output is correct |
64 |
Correct |
1408 ms |
62988 KB |
Output is correct |
65 |
Correct |
1354 ms |
63060 KB |
Output is correct |
66 |
Correct |
1589 ms |
63400 KB |
Output is correct |
67 |
Correct |
1603 ms |
63432 KB |
Output is correct |
68 |
Correct |
1734 ms |
72852 KB |
Output is correct |
69 |
Correct |
492 ms |
76848 KB |
Output is correct |
70 |
Correct |
1055 ms |
71680 KB |
Output is correct |
71 |
Correct |
1054 ms |
71636 KB |
Output is correct |
72 |
Correct |
1041 ms |
71508 KB |
Output is correct |
73 |
Correct |
985 ms |
71616 KB |
Output is correct |
74 |
Correct |
1030 ms |
71476 KB |
Output is correct |
75 |
Correct |
984 ms |
71436 KB |
Output is correct |