#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
#define vec vector
const int INF = 1e9;
struct SegNode {
int mx = -INF;
int mn = INF;
SegNode merge(SegNode other) {
return {max(mx, other.mx), min(mn, other.mn)};
}
};
struct SegTree {
vec<SegNode> data;
vec<int> lazy;
vec<pair<SegNode, int>> suff_cache;
vec<pair<SegNode, int>> pref_cache;
int n;
int upd_ind = 1;
SegTree(vec<int> init_data) {
n = 1;
while(n<init_data.size()) n*=2;
data = vec<SegNode>(n*2);
lazy = vec(n*2, 0);
suff_cache = vec<pair<SegNode, int>>(n);
pref_cache = vec<pair<SegNode, int>>(n);
for(int i = 0; i<init_data.size(); i++) {
data[i+n] = {init_data[i], init_data[i]};
}
for(int i = n-1; i > 0; i--) {
data[i] = data[i*2].merge(data[i*2+1]);
}
}
SegNode query_suffix(int l) {
if(suff_cache[l].second != upd_ind) suff_cache[l] = {query(l, n), upd_ind};
return suff_cache[l].first;
}
SegNode query_prefix(int r) {
if(pref_cache[r-1].second != upd_ind) pref_cache[r-1] = {query(0, r), upd_ind};
return pref_cache[r-1].first;
}
void push(int i) {
data[i].mx += lazy[i];
data[i].mn += lazy[i];
if(i*2 > n*2) {
lazy[i] = 0;
return;
}
lazy[i*2] += lazy[i];
lazy[i*2+1] += lazy[i];
lazy[i] = 0;
}
SegNode query(int l, int r, int i = 1, int ll = 0, int rr = -1) {
if(rr == -1) rr = n;
push(i);
if(ll >= r || rr <= l) return {};
if(ll >= l && rr <= r) return data[i];
int mm = (ll+rr)/2;
return query(l, r, i*2, ll, mm).merge(query(l, r, i*2+1, mm, rr));
}
void upd(int l, int r, int val, int i = 1, int ll = 0, int rr = -1) {
upd_ind++;
if(rr == -1) rr = n;
push(i);
if(ll >= r || rr <= l) return;
if(ll >= l && rr <= r) {
lazy[i] += val;
push(i);
return;
}
int mm = (ll+rr)/2;
upd(l, r, val, i*2, ll, mm);
upd(l, r, val, i*2+1, mm, rr);
data[i] = data[i*2].merge(data[i*2+1]);
}
};
int sequence(int n, std::vector<int> a) {
int ans = 0;
vec<vec<int>> val_inds(n+1);
for(int i = 0; i<n; i++) {
val_inds[a[i]].push_back(i);
}
vec<int> st1_init(n+1);
vec<int> st2_init(n+1);
iota(st1_init.begin(), st1_init.end(), 0);
iota(st2_init.begin(), st2_init.end(), 0);
SegTree st1(st1_init);
SegTree st2(st2_init);
for(int i = 1; i<=n; i++) {
for(int j = 0; j<val_inds[i-1].size(); j++) {
st1.upd(val_inds[i-1][j]+1, n+1, -2);
}
for(int j = 0; j<val_inds[i].size(); j++) {
st2.upd(val_inds[i][j]+1, n+1, -2);
}
int k_l = 1;
int k_r = val_inds[i].size()+1;
while(k_l < k_r) {
int k = (k_l+k_r)/2;
bool found = false;
for(int j = k-1; j<val_inds[i].size(); j++) {
int l = val_inds[i][j-(k-1)];
int r = val_inds[i][j]+1;
if(st1.query_suffix(r).mx - st1.query_prefix(l+1).mn >= 0 &&
st2.query_suffix(r).mn - st2.query_prefix(l+1).mx <= 0) {
ans = max(ans, k);
found = true;
break;
}
}
if(found) k_l = k+1;
else k_r = k;
}
}
return ans;
}
Compilation message
sequence.cpp: In constructor 'SegTree::SegTree(std::vector<int>)':
sequence.cpp:31:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | while(n<init_data.size()) n*=2;
| ~^~~~~~~~~~~~~~~~~
sequence.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i = 0; i<init_data.size(); i++) {
| ~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:124:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int j = 0; j<val_inds[i-1].size(); j++) {
| ~^~~~~~~~~~~~~~~~~~~~~
sequence.cpp:128:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int j = 0; j<val_inds[i].size(); j++) {
| ~^~~~~~~~~~~~~~~~~~~
sequence.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int j = k-1; j<val_inds[i].size(); j++) {
| ~^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
432 KB |
Output is correct |
3 |
Correct |
0 ms |
600 KB |
Output is correct |
4 |
Correct |
0 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 |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
448 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
432 KB |
Output is correct |
3 |
Correct |
0 ms |
600 KB |
Output is correct |
4 |
Correct |
0 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 |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
448 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 |
600 KB |
Output is correct |
14 |
Correct |
3 ms |
760 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
744 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 |
600 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
891 ms |
84396 KB |
Output is correct |
3 |
Correct |
910 ms |
84396 KB |
Output is correct |
4 |
Correct |
567 ms |
74028 KB |
Output is correct |
5 |
Correct |
829 ms |
83224 KB |
Output is correct |
6 |
Correct |
830 ms |
83628 KB |
Output is correct |
7 |
Correct |
596 ms |
75108 KB |
Output is correct |
8 |
Correct |
672 ms |
75184 KB |
Output is correct |
9 |
Correct |
548 ms |
74044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
432 KB |
Output is correct |
2 |
Correct |
565 ms |
74328 KB |
Output is correct |
3 |
Correct |
627 ms |
74008 KB |
Output is correct |
4 |
Correct |
761 ms |
74204 KB |
Output is correct |
5 |
Correct |
727 ms |
74452 KB |
Output is correct |
6 |
Correct |
707 ms |
73980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1219 ms |
90028 KB |
Output is correct |
2 |
Correct |
1237 ms |
90032 KB |
Output is correct |
3 |
Correct |
1172 ms |
89516 KB |
Output is correct |
4 |
Correct |
1200 ms |
89612 KB |
Output is correct |
5 |
Correct |
1062 ms |
86188 KB |
Output is correct |
6 |
Correct |
1020 ms |
86316 KB |
Output is correct |
7 |
Correct |
924 ms |
84908 KB |
Output is correct |
8 |
Correct |
857 ms |
84652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
432 KB |
Output is correct |
3 |
Correct |
0 ms |
600 KB |
Output is correct |
4 |
Correct |
0 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 |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
448 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 |
600 KB |
Output is correct |
14 |
Correct |
3 ms |
760 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
744 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 |
600 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 |
165 ms |
18208 KB |
Output is correct |
24 |
Correct |
138 ms |
18276 KB |
Output is correct |
25 |
Correct |
162 ms |
18284 KB |
Output is correct |
26 |
Correct |
145 ms |
17068 KB |
Output is correct |
27 |
Correct |
138 ms |
17184 KB |
Output is correct |
28 |
Correct |
130 ms |
17180 KB |
Output is correct |
29 |
Correct |
132 ms |
16672 KB |
Output is correct |
30 |
Correct |
117 ms |
16692 KB |
Output is correct |
31 |
Correct |
79 ms |
16792 KB |
Output is correct |
32 |
Correct |
123 ms |
18976 KB |
Output is correct |
33 |
Correct |
144 ms |
17948 KB |
Output is correct |
34 |
Correct |
145 ms |
17948 KB |
Output is correct |
35 |
Correct |
171 ms |
18036 KB |
Output is correct |
36 |
Correct |
156 ms |
17948 KB |
Output is correct |
37 |
Correct |
133 ms |
18072 KB |
Output is correct |
38 |
Correct |
142 ms |
17948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
432 KB |
Output is correct |
3 |
Correct |
0 ms |
600 KB |
Output is correct |
4 |
Correct |
0 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 |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
448 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 |
600 KB |
Output is correct |
14 |
Correct |
3 ms |
760 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
744 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 |
600 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 |
891 ms |
84396 KB |
Output is correct |
24 |
Correct |
910 ms |
84396 KB |
Output is correct |
25 |
Correct |
567 ms |
74028 KB |
Output is correct |
26 |
Correct |
829 ms |
83224 KB |
Output is correct |
27 |
Correct |
830 ms |
83628 KB |
Output is correct |
28 |
Correct |
596 ms |
75108 KB |
Output is correct |
29 |
Correct |
672 ms |
75184 KB |
Output is correct |
30 |
Correct |
548 ms |
74044 KB |
Output is correct |
31 |
Correct |
565 ms |
74328 KB |
Output is correct |
32 |
Correct |
627 ms |
74008 KB |
Output is correct |
33 |
Correct |
761 ms |
74204 KB |
Output is correct |
34 |
Correct |
727 ms |
74452 KB |
Output is correct |
35 |
Correct |
707 ms |
73980 KB |
Output is correct |
36 |
Correct |
1219 ms |
90028 KB |
Output is correct |
37 |
Correct |
1237 ms |
90032 KB |
Output is correct |
38 |
Correct |
1172 ms |
89516 KB |
Output is correct |
39 |
Correct |
1200 ms |
89612 KB |
Output is correct |
40 |
Correct |
1062 ms |
86188 KB |
Output is correct |
41 |
Correct |
1020 ms |
86316 KB |
Output is correct |
42 |
Correct |
924 ms |
84908 KB |
Output is correct |
43 |
Correct |
857 ms |
84652 KB |
Output is correct |
44 |
Correct |
165 ms |
18208 KB |
Output is correct |
45 |
Correct |
138 ms |
18276 KB |
Output is correct |
46 |
Correct |
162 ms |
18284 KB |
Output is correct |
47 |
Correct |
145 ms |
17068 KB |
Output is correct |
48 |
Correct |
138 ms |
17184 KB |
Output is correct |
49 |
Correct |
130 ms |
17180 KB |
Output is correct |
50 |
Correct |
132 ms |
16672 KB |
Output is correct |
51 |
Correct |
117 ms |
16692 KB |
Output is correct |
52 |
Correct |
79 ms |
16792 KB |
Output is correct |
53 |
Correct |
123 ms |
18976 KB |
Output is correct |
54 |
Correct |
144 ms |
17948 KB |
Output is correct |
55 |
Correct |
145 ms |
17948 KB |
Output is correct |
56 |
Correct |
171 ms |
18036 KB |
Output is correct |
57 |
Correct |
156 ms |
17948 KB |
Output is correct |
58 |
Correct |
133 ms |
18072 KB |
Output is correct |
59 |
Correct |
142 ms |
17948 KB |
Output is correct |
60 |
Correct |
1335 ms |
84484 KB |
Output is correct |
61 |
Correct |
1350 ms |
84472 KB |
Output is correct |
62 |
Correct |
1355 ms |
84336 KB |
Output is correct |
63 |
Correct |
1173 ms |
76336 KB |
Output is correct |
64 |
Correct |
1091 ms |
76328 KB |
Output is correct |
65 |
Correct |
1180 ms |
76108 KB |
Output is correct |
66 |
Correct |
851 ms |
74232 KB |
Output is correct |
67 |
Correct |
757 ms |
74168 KB |
Output is correct |
68 |
Correct |
454 ms |
76632 KB |
Output is correct |
69 |
Correct |
930 ms |
90220 KB |
Output is correct |
70 |
Correct |
1276 ms |
83568 KB |
Output is correct |
71 |
Correct |
1157 ms |
83236 KB |
Output is correct |
72 |
Correct |
1160 ms |
82728 KB |
Output is correct |
73 |
Correct |
1371 ms |
83248 KB |
Output is correct |
74 |
Correct |
1284 ms |
82896 KB |
Output is correct |
75 |
Correct |
1234 ms |
83240 KB |
Output is correct |