#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
using ii = pair<int, int>;
template <class T, T (*merge)(T, T), T def = T()>
struct Segtree {
vector<T> tree, lazy;
int _n;
Segtree() {}
Segtree(int N){
setup(N);
}
void setup(int N){
tree.assign(4 * N, T());
lazy.assign(4 * N, T());
_n = N;
}
void apply(int i, T delta){
tree[i] += delta;
lazy[i] += delta;
}
void push(int i){
if (lazy[i] == T()) return;
apply(i<<1, lazy[i]);
apply(i<<1|1, lazy[i]);
lazy[i] = T();
}
void update(int tl, int tr, T delta){
update(1, 0, _n - 1, tl, tr, delta);
}
void update(int i, int l, int r, int tl, int tr, T delta){
if (tl <= l && r <= tr){
apply(i, delta);
return;
}
if (tl > r || tr < l) return;
push(i);
int mid = (l + r) >> 1;
update(i<<1, l, mid, tl, tr, delta);
update(i<<1|1, mid+1, r, tl, tr, delta);
tree[i] = merge(tree[i<<1], tree[i<<1|1]);
}
T get(int tl, int tr){
return get(1, 0, _n - 1, tl, tr);
}
T get(int i, int l, int r, int tl, int tr){
if (tl <= l && r <= tr) return tree[i];
if (tl > r || tr < l) return def;
push(i);
int mid = (l + r) >> 1;
T resl = get(i<<1, l, mid, tl, tr);
T resr = get(i<<1|1, mid+1, r, tl, tr);
return merge(resl, resr);
}
};
template <class T = int>
T fmin(T a, T b) { return min(a, b); }
template <class T = int>
T fmax(T a, T b) { return max(a, b); }
Segtree<int, fmin, inf> stmin;
Segtree<int, fmax, -inf> stmax;
int sequence(int N, vector<int> A){
vector<vector<int>> locations(N + 1);
for (int i = 0; i < N; i++) locations[A[i]].push_back(i + 1);
stmin.setup(N + 1);
stmax.setup(N + 1);
for (int i = 1; i <= N; i++) stmin.update(i, N, 1);
for (int i = 1; i <= N; i++) stmax.update(i, N, 1);
auto is_intersect = [&](ii p1, ii p2){
if (p1.first > p2.first) swap(p1, p2);
return p1.second >= p2.first;
};
int ans = 0;
for (int num = 1; num <= N; num++){
if (locations[num].empty()) continue;
for (auto j: locations[num]) stmin.update(j, N, -2);
for (auto j: locations[num]) stmax.update(j, N, -2);
for (int idxl = (int)locations[num].size() - 1; idxl >= 0; idxl--){
int l = locations[num][idxl];
stmin.update(l, N, 2);
stmax.update(l, N, 2);
for (int idxr = idxl + ans; idxr < (int)locations[num].size(); idxr++){
int r = locations[num][idxr];
ii range_lhs = {stmin.get(0, l - 1), stmax.get(0, l - 1)};
ii range_rhs = {stmin.get(r, N) - 2 * (ans + 1), stmax.get(r, N)};
if (is_intersect(range_lhs, range_rhs)){
ans++;
}
else break;
}
}
for (auto j: locations[num]) stmin.update(j, N, -2);
for (auto j: locations[num]) stmax.update(j, N, -2);
}
return ans;
}
#ifdef LOCAL
int main(){
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
cout << "Answer: " << sequence(n, a) << "\n";
}
#endif // LOCAL
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
3 ms |
604 KB |
Output is correct |
14 |
Correct |
3 ms |
604 KB |
Output is correct |
15 |
Correct |
3 ms |
856 KB |
Output is correct |
16 |
Correct |
3 ms |
604 KB |
Output is correct |
17 |
Correct |
3 ms |
604 KB |
Output is correct |
18 |
Correct |
3 ms |
604 KB |
Output is correct |
19 |
Correct |
3 ms |
668 KB |
Output is correct |
20 |
Correct |
3 ms |
600 KB |
Output is correct |
21 |
Correct |
3 ms |
604 KB |
Output is correct |
22 |
Correct |
3 ms |
664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
901 ms |
59136 KB |
Output is correct |
3 |
Correct |
908 ms |
60644 KB |
Output is correct |
4 |
Correct |
944 ms |
50484 KB |
Output is correct |
5 |
Correct |
893 ms |
59616 KB |
Output is correct |
6 |
Correct |
917 ms |
59732 KB |
Output is correct |
7 |
Correct |
858 ms |
51284 KB |
Output is correct |
8 |
Correct |
892 ms |
51444 KB |
Output is correct |
9 |
Correct |
1002 ms |
50536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1031 ms |
49644 KB |
Output is correct |
3 |
Correct |
1104 ms |
50488 KB |
Output is correct |
4 |
Correct |
1052 ms |
50492 KB |
Output is correct |
5 |
Correct |
1142 ms |
50616 KB |
Output is correct |
6 |
Correct |
1092 ms |
50572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1147 ms |
63064 KB |
Output is correct |
2 |
Correct |
1120 ms |
66360 KB |
Output is correct |
3 |
Correct |
1157 ms |
65764 KB |
Output is correct |
4 |
Correct |
1144 ms |
65768 KB |
Output is correct |
5 |
Correct |
1166 ms |
62352 KB |
Output is correct |
6 |
Correct |
1042 ms |
62360 KB |
Output is correct |
7 |
Correct |
992 ms |
61180 KB |
Output is correct |
8 |
Correct |
952 ms |
61008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
3 ms |
604 KB |
Output is correct |
14 |
Correct |
3 ms |
604 KB |
Output is correct |
15 |
Correct |
3 ms |
856 KB |
Output is correct |
16 |
Correct |
3 ms |
604 KB |
Output is correct |
17 |
Correct |
3 ms |
604 KB |
Output is correct |
18 |
Correct |
3 ms |
604 KB |
Output is correct |
19 |
Correct |
3 ms |
668 KB |
Output is correct |
20 |
Correct |
3 ms |
600 KB |
Output is correct |
21 |
Correct |
3 ms |
604 KB |
Output is correct |
22 |
Correct |
3 ms |
664 KB |
Output is correct |
23 |
Correct |
148 ms |
9820 KB |
Output is correct |
24 |
Correct |
158 ms |
10068 KB |
Output is correct |
25 |
Correct |
147 ms |
10008 KB |
Output is correct |
26 |
Correct |
162 ms |
8900 KB |
Output is correct |
27 |
Correct |
177 ms |
8908 KB |
Output is correct |
28 |
Correct |
173 ms |
8892 KB |
Output is correct |
29 |
Correct |
146 ms |
8512 KB |
Output is correct |
30 |
Correct |
157 ms |
8348 KB |
Output is correct |
31 |
Correct |
156 ms |
8660 KB |
Output is correct |
32 |
Correct |
127 ms |
10840 KB |
Output is correct |
33 |
Correct |
153 ms |
9816 KB |
Output is correct |
34 |
Correct |
177 ms |
9820 KB |
Output is correct |
35 |
Correct |
158 ms |
9764 KB |
Output is correct |
36 |
Correct |
162 ms |
9772 KB |
Output is correct |
37 |
Correct |
169 ms |
9788 KB |
Output is correct |
38 |
Correct |
164 ms |
9664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
3 ms |
604 KB |
Output is correct |
14 |
Correct |
3 ms |
604 KB |
Output is correct |
15 |
Correct |
3 ms |
856 KB |
Output is correct |
16 |
Correct |
3 ms |
604 KB |
Output is correct |
17 |
Correct |
3 ms |
604 KB |
Output is correct |
18 |
Correct |
3 ms |
604 KB |
Output is correct |
19 |
Correct |
3 ms |
668 KB |
Output is correct |
20 |
Correct |
3 ms |
600 KB |
Output is correct |
21 |
Correct |
3 ms |
604 KB |
Output is correct |
22 |
Correct |
3 ms |
664 KB |
Output is correct |
23 |
Correct |
901 ms |
59136 KB |
Output is correct |
24 |
Correct |
908 ms |
60644 KB |
Output is correct |
25 |
Correct |
944 ms |
50484 KB |
Output is correct |
26 |
Correct |
893 ms |
59616 KB |
Output is correct |
27 |
Correct |
917 ms |
59732 KB |
Output is correct |
28 |
Correct |
858 ms |
51284 KB |
Output is correct |
29 |
Correct |
892 ms |
51444 KB |
Output is correct |
30 |
Correct |
1002 ms |
50536 KB |
Output is correct |
31 |
Correct |
1031 ms |
49644 KB |
Output is correct |
32 |
Correct |
1104 ms |
50488 KB |
Output is correct |
33 |
Correct |
1052 ms |
50492 KB |
Output is correct |
34 |
Correct |
1142 ms |
50616 KB |
Output is correct |
35 |
Correct |
1092 ms |
50572 KB |
Output is correct |
36 |
Correct |
1147 ms |
63064 KB |
Output is correct |
37 |
Correct |
1120 ms |
66360 KB |
Output is correct |
38 |
Correct |
1157 ms |
65764 KB |
Output is correct |
39 |
Correct |
1144 ms |
65768 KB |
Output is correct |
40 |
Correct |
1166 ms |
62352 KB |
Output is correct |
41 |
Correct |
1042 ms |
62360 KB |
Output is correct |
42 |
Correct |
992 ms |
61180 KB |
Output is correct |
43 |
Correct |
952 ms |
61008 KB |
Output is correct |
44 |
Correct |
148 ms |
9820 KB |
Output is correct |
45 |
Correct |
158 ms |
10068 KB |
Output is correct |
46 |
Correct |
147 ms |
10008 KB |
Output is correct |
47 |
Correct |
162 ms |
8900 KB |
Output is correct |
48 |
Correct |
177 ms |
8908 KB |
Output is correct |
49 |
Correct |
173 ms |
8892 KB |
Output is correct |
50 |
Correct |
146 ms |
8512 KB |
Output is correct |
51 |
Correct |
157 ms |
8348 KB |
Output is correct |
52 |
Correct |
156 ms |
8660 KB |
Output is correct |
53 |
Correct |
127 ms |
10840 KB |
Output is correct |
54 |
Correct |
153 ms |
9816 KB |
Output is correct |
55 |
Correct |
177 ms |
9820 KB |
Output is correct |
56 |
Correct |
158 ms |
9764 KB |
Output is correct |
57 |
Correct |
162 ms |
9772 KB |
Output is correct |
58 |
Correct |
169 ms |
9788 KB |
Output is correct |
59 |
Correct |
164 ms |
9664 KB |
Output is correct |
60 |
Correct |
1359 ms |
60648 KB |
Output is correct |
61 |
Correct |
1280 ms |
60640 KB |
Output is correct |
62 |
Correct |
1296 ms |
60500 KB |
Output is correct |
63 |
Correct |
1320 ms |
52492 KB |
Output is correct |
64 |
Correct |
1265 ms |
52484 KB |
Output is correct |
65 |
Correct |
1313 ms |
52464 KB |
Output is correct |
66 |
Correct |
1052 ms |
50416 KB |
Output is correct |
67 |
Correct |
1027 ms |
50784 KB |
Output is correct |
68 |
Correct |
1121 ms |
52928 KB |
Output is correct |
69 |
Correct |
891 ms |
66380 KB |
Output is correct |
70 |
Correct |
1235 ms |
59724 KB |
Output is correct |
71 |
Correct |
1210 ms |
59664 KB |
Output is correct |
72 |
Correct |
1233 ms |
59064 KB |
Output is correct |
73 |
Correct |
1207 ms |
59404 KB |
Output is correct |
74 |
Correct |
1161 ms |
59080 KB |
Output is correct |
75 |
Correct |
1247 ms |
59404 KB |
Output is correct |