#include "sequence.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using dii = tuple<double, int, int>;
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define ppb pop_back
vector<int> vec[500005];
vector<iii> ev;
vector<ii> upd, qu;
set<ii> ds;
vector<set<ii>::iterator> to_erase;
int idx = 1, S[1000005], E[1000005], lft[1000005], rig[1000005], mx[1000005], mi[1000005], pv[1000005], l0[500005], l1[500005], r0[500005], r1[500005];
namespace root {
void build(int l, int r, int p = 1) {
//~ cout << "@ " << p << ' ' << l << ' ' << r << '\n';
S[p] = l;
E[p] = r;
if (l == r) {
mx[p] = mi[p] = -l;
return;
}
int M = (l + r) >> 1;
if (l <= M) {
lft[p] = ++idx;
build(l, M, lft[p]);
}
if (M + 1 <= r) {
rig[p] = ++idx;
build(M + 1, r, rig[p]);
}
mi[p] = min(mi[lft[p]], mi[rig[p]]);
mx[p] = max(mx[lft[p]], mx[rig[p]]);
}
void prop(int p) {
if (S[p] == E[p] || !pv[p]) return;
mi[lft[p]] += pv[p];
mx[lft[p]] += pv[p];
pv[lft[p]] += pv[p];
mi[rig[p]] += pv[p];
mx[rig[p]] += pv[p];
pv[rig[p]] += pv[p];
pv[p] = 0;
}
ii qry(int l, int r, int p = 1) {
if (l > E[p] || r < S[p]) return mp((int)1e9, (int)-1e9);
if (l <= S[p] && E[p] <= r) return mp(mi[p], mx[p]);
prop(p);
ii lq = qry(l, r, lft[p]), rq = qry(l, r, rig[p]);
return mp(min(lq.first, rq.first), max(lq.second, rq.second));
}
void upd(int l, int r, int v, int p = 1) {
if (l > E[p] || r < S[p]) return;
if (l <= S[p] && E[p] <= r) {
mi[p] += v;
mx[p] += v;
pv[p] += v;
return;
}
prop(p);
upd(l, r, v, lft[p]);
upd(l, r, v, rig[p]);
mi[p] = min(mi[lft[p]], mi[rig[p]]);
mx[p] = max(mx[lft[p]], mx[rig[p]]);
}
};
int sequence(int N, vector<int> A) {
int ans = 0;
root::build(0, N - 1);
for (int i = 0; i < N; i++) {
vec[A[i]].pb(i);
}
for (int i = 1; i <= N; i++) {
if (vec[i].empty()) continue;
// process v = i
for (int j = 0; j < vec[i].size(); j++) {
l0[j] = 1;
r0[j] = 1;
if (vec[i][j] > 0) {
auto tmp = root::qry(0, vec[i][j] - 1);
l0[j] = min(l0[j], tmp.first);
r0[j] = max(r0[j], tmp.second);
}
}
for (int j = (int)vec[i].size() - 1; j >= 0; j--) {
l1[j] = (int)1e9;
r1[j] = -(int)1e9;
auto tmp = root::qry(vec[i][j], N - 1);
l1[j] = min(l1[j], tmp.first);
r1[j] = max(r1[j], tmp.second);
}
ev.clear();
for (int j = 0; j < vec[i].size(); j++) {
if (l0[j] <= r0[j]) {
ev.eb(l0[j], 0, j);
ev.eb(r0[j], 1, j);
}
if (l1[j] <= r1[j]) {
ev.eb(l1[j], -2, j);
ev.eb(r1[j], 3, j);
}
}
sort(ev.begin(), ev.end());
multiset<int> m1, m2;
for (auto [x, t, idx] : ev) {
if (0 <= t && t <= 1) {
if (!m2.empty()) {
ans = max(ans, *m2.rbegin() - idx + 1);
}
} else {
if (!m1.empty()) {
ans = max(ans, idx - *m1.begin() + 1);
}
}
if (t == 0) m1.insert(idx);
else if (t == 1) m1.erase(m1.find(idx));
else if (t == -2) m2.insert(idx);
else if (t == 3) m2.erase(m2.find(idx));
}
upd.clear();
qu.clear();
for (int j = 0; j < vec[i].size(); j++) {
upd.eb(l0[j], j);
qu.eb(r1[j], j);
}
ds.clear();
to_erase.clear();
sort(upd.begin(), upd.end(), greater<ii>());
sort(qu.begin(), qu.end(), greater<ii>());
for (int pt1 = 0, pt2 = 0; pt1 < upd.size() || pt2 < qu.size(); ) {
if ((pt1 < upd.size() && pt2 < qu.size() && upd[pt1].first > qu[pt2].first) || (pt2 >= qu.size())) {
// do upd
int x = upd[pt1].first + 2 * upd[pt1].second, y = upd[pt1].second;
auto it = ds.upper_bound(mp(x, (int)1e9));
if (it != ds.begin()) {
--it;
if (it->second <= y) goto done;
if (it->first < x) ++it;
}
while (it != ds.end() && it->second >= y) {
to_erase.pb(it);
++it;
}
for (auto it : to_erase) {
ds.erase(it);
}
to_erase.clear();
ds.emplace(x, y);
done:;
pt1++;
} else {
// do qu
int x = qu[pt2].first + 2 * qu[pt2].second + 2;
auto it = ds.upper_bound(mp(x, (int)1e9));
if (it != ds.begin()) {
--it;
ans = max(ans, qu[pt2].second - it->second + 1);
}
pt2++;
}
}
for (int j : vec[i]) {
root::upd(j, N - 1, 2);
}
}
return ans;
}
Compilation message
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int j = 0; j < vec[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
sequence.cpp:111:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int j = 0; j < vec[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
sequence.cpp:140:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for (int j = 0; j < vec[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
sequence.cpp:148:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for (int pt1 = 0, pt2 = 0; pt1 < upd.size() || pt2 < qu.size(); ) {
| ~~~~^~~~~~~~~~~~
sequence.cpp:148:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for (int pt1 = 0, pt2 = 0; pt1 < upd.size() || pt2 < qu.size(); ) {
| ~~~~^~~~~~~~~~~
sequence.cpp:149:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | if ((pt1 < upd.size() && pt2 < qu.size() && upd[pt1].first > qu[pt2].first) || (pt2 >= qu.size())) {
| ~~~~^~~~~~~~~~~~
sequence.cpp:149:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | if ((pt1 < upd.size() && pt2 < qu.size() && upd[pt1].first > qu[pt2].first) || (pt2 >= qu.size())) {
| ~~~~^~~~~~~~~~~
sequence.cpp:149:88: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | if ((pt1 < upd.size() && pt2 < qu.size() && upd[pt1].first > qu[pt2].first) || (pt2 >= qu.size())) {
| ~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12032 KB |
Output is correct |
2 |
Correct |
6 ms |
12048 KB |
Output is correct |
3 |
Correct |
5 ms |
12044 KB |
Output is correct |
4 |
Correct |
5 ms |
12044 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12032 KB |
Output is correct |
7 |
Correct |
5 ms |
12116 KB |
Output is correct |
8 |
Correct |
6 ms |
12116 KB |
Output is correct |
9 |
Correct |
7 ms |
12048 KB |
Output is correct |
10 |
Correct |
7 ms |
12044 KB |
Output is correct |
11 |
Correct |
6 ms |
12116 KB |
Output is correct |
12 |
Correct |
6 ms |
12116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12032 KB |
Output is correct |
2 |
Correct |
6 ms |
12048 KB |
Output is correct |
3 |
Correct |
5 ms |
12044 KB |
Output is correct |
4 |
Correct |
5 ms |
12044 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12032 KB |
Output is correct |
7 |
Correct |
5 ms |
12116 KB |
Output is correct |
8 |
Correct |
6 ms |
12116 KB |
Output is correct |
9 |
Correct |
7 ms |
12048 KB |
Output is correct |
10 |
Correct |
7 ms |
12044 KB |
Output is correct |
11 |
Correct |
6 ms |
12116 KB |
Output is correct |
12 |
Correct |
6 ms |
12116 KB |
Output is correct |
13 |
Correct |
9 ms |
12304 KB |
Output is correct |
14 |
Correct |
8 ms |
12244 KB |
Output is correct |
15 |
Correct |
7 ms |
12244 KB |
Output is correct |
16 |
Correct |
8 ms |
12244 KB |
Output is correct |
17 |
Correct |
7 ms |
12244 KB |
Output is correct |
18 |
Correct |
7 ms |
12308 KB |
Output is correct |
19 |
Correct |
10 ms |
12244 KB |
Output is correct |
20 |
Correct |
8 ms |
12312 KB |
Output is correct |
21 |
Correct |
7 ms |
12328 KB |
Output is correct |
22 |
Correct |
7 ms |
12340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12032 KB |
Output is correct |
2 |
Correct |
512 ms |
56604 KB |
Output is correct |
3 |
Correct |
486 ms |
56616 KB |
Output is correct |
4 |
Correct |
711 ms |
64060 KB |
Output is correct |
5 |
Correct |
511 ms |
55488 KB |
Output is correct |
6 |
Correct |
507 ms |
55588 KB |
Output is correct |
7 |
Correct |
568 ms |
48780 KB |
Output is correct |
8 |
Correct |
625 ms |
48904 KB |
Output is correct |
9 |
Correct |
727 ms |
74748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12048 KB |
Output is correct |
2 |
Correct |
781 ms |
79796 KB |
Output is correct |
3 |
Correct |
778 ms |
71368 KB |
Output is correct |
4 |
Correct |
760 ms |
71380 KB |
Output is correct |
5 |
Correct |
763 ms |
86120 KB |
Output is correct |
6 |
Correct |
781 ms |
83708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
732 ms |
62336 KB |
Output is correct |
2 |
Correct |
741 ms |
62344 KB |
Output is correct |
3 |
Correct |
736 ms |
61752 KB |
Output is correct |
4 |
Correct |
724 ms |
61800 KB |
Output is correct |
5 |
Correct |
647 ms |
58332 KB |
Output is correct |
6 |
Correct |
594 ms |
58332 KB |
Output is correct |
7 |
Correct |
458 ms |
57152 KB |
Output is correct |
8 |
Correct |
480 ms |
56724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12032 KB |
Output is correct |
2 |
Correct |
6 ms |
12048 KB |
Output is correct |
3 |
Correct |
5 ms |
12044 KB |
Output is correct |
4 |
Correct |
5 ms |
12044 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12032 KB |
Output is correct |
7 |
Correct |
5 ms |
12116 KB |
Output is correct |
8 |
Correct |
6 ms |
12116 KB |
Output is correct |
9 |
Correct |
7 ms |
12048 KB |
Output is correct |
10 |
Correct |
7 ms |
12044 KB |
Output is correct |
11 |
Correct |
6 ms |
12116 KB |
Output is correct |
12 |
Correct |
6 ms |
12116 KB |
Output is correct |
13 |
Correct |
9 ms |
12304 KB |
Output is correct |
14 |
Correct |
8 ms |
12244 KB |
Output is correct |
15 |
Correct |
7 ms |
12244 KB |
Output is correct |
16 |
Correct |
8 ms |
12244 KB |
Output is correct |
17 |
Correct |
7 ms |
12244 KB |
Output is correct |
18 |
Correct |
7 ms |
12308 KB |
Output is correct |
19 |
Correct |
10 ms |
12244 KB |
Output is correct |
20 |
Correct |
8 ms |
12312 KB |
Output is correct |
21 |
Correct |
7 ms |
12328 KB |
Output is correct |
22 |
Correct |
7 ms |
12340 KB |
Output is correct |
23 |
Correct |
102 ms |
19096 KB |
Output is correct |
24 |
Correct |
103 ms |
19092 KB |
Output is correct |
25 |
Correct |
103 ms |
19272 KB |
Output is correct |
26 |
Correct |
122 ms |
18132 KB |
Output is correct |
27 |
Correct |
110 ms |
18036 KB |
Output is correct |
28 |
Correct |
108 ms |
18124 KB |
Output is correct |
29 |
Correct |
101 ms |
20084 KB |
Output is correct |
30 |
Correct |
112 ms |
20172 KB |
Output is correct |
31 |
Correct |
103 ms |
26648 KB |
Output is correct |
32 |
Correct |
68 ms |
19996 KB |
Output is correct |
33 |
Correct |
102 ms |
19960 KB |
Output is correct |
34 |
Correct |
100 ms |
20324 KB |
Output is correct |
35 |
Correct |
111 ms |
20328 KB |
Output is correct |
36 |
Correct |
121 ms |
20236 KB |
Output is correct |
37 |
Correct |
106 ms |
20124 KB |
Output is correct |
38 |
Correct |
104 ms |
20160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12032 KB |
Output is correct |
2 |
Correct |
6 ms |
12048 KB |
Output is correct |
3 |
Correct |
5 ms |
12044 KB |
Output is correct |
4 |
Correct |
5 ms |
12044 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12032 KB |
Output is correct |
7 |
Correct |
5 ms |
12116 KB |
Output is correct |
8 |
Correct |
6 ms |
12116 KB |
Output is correct |
9 |
Correct |
7 ms |
12048 KB |
Output is correct |
10 |
Correct |
7 ms |
12044 KB |
Output is correct |
11 |
Correct |
6 ms |
12116 KB |
Output is correct |
12 |
Correct |
6 ms |
12116 KB |
Output is correct |
13 |
Correct |
9 ms |
12304 KB |
Output is correct |
14 |
Correct |
8 ms |
12244 KB |
Output is correct |
15 |
Correct |
7 ms |
12244 KB |
Output is correct |
16 |
Correct |
8 ms |
12244 KB |
Output is correct |
17 |
Correct |
7 ms |
12244 KB |
Output is correct |
18 |
Correct |
7 ms |
12308 KB |
Output is correct |
19 |
Correct |
10 ms |
12244 KB |
Output is correct |
20 |
Correct |
8 ms |
12312 KB |
Output is correct |
21 |
Correct |
7 ms |
12328 KB |
Output is correct |
22 |
Correct |
7 ms |
12340 KB |
Output is correct |
23 |
Correct |
512 ms |
56604 KB |
Output is correct |
24 |
Correct |
486 ms |
56616 KB |
Output is correct |
25 |
Correct |
711 ms |
64060 KB |
Output is correct |
26 |
Correct |
511 ms |
55488 KB |
Output is correct |
27 |
Correct |
507 ms |
55588 KB |
Output is correct |
28 |
Correct |
568 ms |
48780 KB |
Output is correct |
29 |
Correct |
625 ms |
48904 KB |
Output is correct |
30 |
Correct |
727 ms |
74748 KB |
Output is correct |
31 |
Correct |
781 ms |
79796 KB |
Output is correct |
32 |
Correct |
778 ms |
71368 KB |
Output is correct |
33 |
Correct |
760 ms |
71380 KB |
Output is correct |
34 |
Correct |
763 ms |
86120 KB |
Output is correct |
35 |
Correct |
781 ms |
83708 KB |
Output is correct |
36 |
Correct |
732 ms |
62336 KB |
Output is correct |
37 |
Correct |
741 ms |
62344 KB |
Output is correct |
38 |
Correct |
736 ms |
61752 KB |
Output is correct |
39 |
Correct |
724 ms |
61800 KB |
Output is correct |
40 |
Correct |
647 ms |
58332 KB |
Output is correct |
41 |
Correct |
594 ms |
58332 KB |
Output is correct |
42 |
Correct |
458 ms |
57152 KB |
Output is correct |
43 |
Correct |
480 ms |
56724 KB |
Output is correct |
44 |
Correct |
102 ms |
19096 KB |
Output is correct |
45 |
Correct |
103 ms |
19092 KB |
Output is correct |
46 |
Correct |
103 ms |
19272 KB |
Output is correct |
47 |
Correct |
122 ms |
18132 KB |
Output is correct |
48 |
Correct |
110 ms |
18036 KB |
Output is correct |
49 |
Correct |
108 ms |
18124 KB |
Output is correct |
50 |
Correct |
101 ms |
20084 KB |
Output is correct |
51 |
Correct |
112 ms |
20172 KB |
Output is correct |
52 |
Correct |
103 ms |
26648 KB |
Output is correct |
53 |
Correct |
68 ms |
19996 KB |
Output is correct |
54 |
Correct |
102 ms |
19960 KB |
Output is correct |
55 |
Correct |
100 ms |
20324 KB |
Output is correct |
56 |
Correct |
111 ms |
20328 KB |
Output is correct |
57 |
Correct |
121 ms |
20236 KB |
Output is correct |
58 |
Correct |
106 ms |
20124 KB |
Output is correct |
59 |
Correct |
104 ms |
20160 KB |
Output is correct |
60 |
Correct |
1048 ms |
56632 KB |
Output is correct |
61 |
Correct |
1130 ms |
56612 KB |
Output is correct |
62 |
Correct |
1094 ms |
56636 KB |
Output is correct |
63 |
Correct |
1112 ms |
48520 KB |
Output is correct |
64 |
Correct |
1068 ms |
48460 KB |
Output is correct |
65 |
Correct |
1044 ms |
48556 KB |
Output is correct |
66 |
Correct |
711 ms |
62160 KB |
Output is correct |
67 |
Correct |
723 ms |
62240 KB |
Output is correct |
68 |
Correct |
703 ms |
103516 KB |
Output is correct |
69 |
Correct |
438 ms |
62296 KB |
Output is correct |
70 |
Correct |
1022 ms |
62052 KB |
Output is correct |
71 |
Correct |
1018 ms |
63428 KB |
Output is correct |
72 |
Correct |
957 ms |
67620 KB |
Output is correct |
73 |
Correct |
1070 ms |
63244 KB |
Output is correct |
74 |
Correct |
1016 ms |
64936 KB |
Output is correct |
75 |
Correct |
1063 ms |
62976 KB |
Output is correct |