#include "sequence.h"
#include <vector>
using namespace std;
#define vi vector<int>
const int siz = 5e5 + 1;
vi his[siz];
#define pi pair<int,int>
#define x first
#define y second
struct node {
int l, r, mid, minl, minr, maxl, maxr,sum1,sum2;
node* sl, * sr;
node(int li, int ri) {
l = li, r = ri, mid = (l + r) / 2, minl = -(r - l + 1), minr = -(r - l + 1), maxl = 0, maxr = 0,sum1=minr,sum2=minr;
if (l < r) {
sl = new node(l, mid);
sr = new node(mid + 1, r);
}
}
void update(int i, int p) {
if (l == r) {
if (p == 2) {
sum1 = 1, minl = 0, minr = 0;
}
else {
sum2 = 1, maxl = 1, maxr = 1;
}
}
else {
if (i <= mid)sl->update(i, p);
else sr->update(i, p);
if (p == 2) {
sum1 = sl->sum1 + sr->sum1;
minl = min(sl->minl, sl->sum1 + sr->minl);
minr = min(sr->minr, sr->sum1 + sl->minr);
}
else {
sum2 = sl->sum2 + sr->sum2;
maxl = max(sl->maxl, sl->sum2 + sr->maxl);
maxr = max(sr->maxr, sr->sum2 + sl->maxr);
}
}
}
int query1(int a, int b) {
if (a <= l && b >= r)return sum1;
if (b <= mid)return min(sl->query1(a, b), sl->query1(a, mid) + sr->minl);
if (a > mid)return min(sr->query1(a, b), sr->query1(mid + 1, b) + sl->minr);
return sl->query1(a, mid) + sr->query1(mid+1, b);
}
int query2(int a, int b) {
if (a <= l && b >= r)return sum2;
if (b <= mid)return max(sl->query2(a, b), sl->query2(a, mid) + sr->maxl);
if (a > mid)return max(sr->query2(a, b), sr->query2(mid + 1, b) + sl->maxr);
return sl->query2(a, mid) + sr->query2(mid+1, b);
}
};
int sequence(int N, std::vector<int> A) {
for (int i = 0; i < N; i++)his[A[i]].push_back(i);
int ans = 1;
node* seg = new node(0, N-1);
for (int i = 0; i <= N; i++) {
if (his[i].empty())continue;
int it1 = 0, it2 = 0;
for (int a : his[i])seg->update(a, 1);
while (it2+1 < his[i].size()) {
if (his[i].size() - it1 <= ans)break;
pi p = { seg->query1(his[i][it1], his[i][it2 + 1]),seg->query2(his[i][it1],his[i][it2 + 1]) };
if (p.x> 0 || p.y< 0) {
it1++;
}
else {
it2++;
}
if (it1 > it2)it2++;
ans = max(ans, it2 - it1 + 1);
}
for (int a : his[i])seg->update(a, 2);
}
return ans;
}
Compilation message
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | while (it2+1 < his[i].size()) {
| ~~~~~~^~~~~~~~~~~~~~~
sequence.cpp:72:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | if (his[i].size() - it1 <= ans)break;
| ~~~~~~~~~~~~~~~~~~~~^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12124 KB |
Output is correct |
2 |
Correct |
4 ms |
12008 KB |
Output is correct |
3 |
Correct |
3 ms |
12124 KB |
Output is correct |
4 |
Correct |
3 ms |
12376 KB |
Output is correct |
5 |
Correct |
5 ms |
12124 KB |
Output is correct |
6 |
Correct |
3 ms |
12124 KB |
Output is correct |
7 |
Correct |
4 ms |
12124 KB |
Output is correct |
8 |
Correct |
3 ms |
12124 KB |
Output is correct |
9 |
Correct |
3 ms |
12124 KB |
Output is correct |
10 |
Correct |
4 ms |
12124 KB |
Output is correct |
11 |
Correct |
3 ms |
12120 KB |
Output is correct |
12 |
Correct |
3 ms |
12124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12124 KB |
Output is correct |
2 |
Correct |
4 ms |
12008 KB |
Output is correct |
3 |
Correct |
3 ms |
12124 KB |
Output is correct |
4 |
Correct |
3 ms |
12376 KB |
Output is correct |
5 |
Correct |
5 ms |
12124 KB |
Output is correct |
6 |
Correct |
3 ms |
12124 KB |
Output is correct |
7 |
Correct |
4 ms |
12124 KB |
Output is correct |
8 |
Correct |
3 ms |
12124 KB |
Output is correct |
9 |
Correct |
3 ms |
12124 KB |
Output is correct |
10 |
Correct |
4 ms |
12124 KB |
Output is correct |
11 |
Correct |
3 ms |
12120 KB |
Output is correct |
12 |
Correct |
3 ms |
12124 KB |
Output is correct |
13 |
Correct |
4 ms |
12376 KB |
Output is correct |
14 |
Correct |
4 ms |
12380 KB |
Output is correct |
15 |
Correct |
5 ms |
12380 KB |
Output is correct |
16 |
Correct |
4 ms |
12380 KB |
Output is correct |
17 |
Correct |
5 ms |
12380 KB |
Output is correct |
18 |
Correct |
4 ms |
12380 KB |
Output is correct |
19 |
Correct |
3 ms |
12380 KB |
Output is correct |
20 |
Correct |
4 ms |
12380 KB |
Output is correct |
21 |
Correct |
4 ms |
12380 KB |
Output is correct |
22 |
Correct |
4 ms |
12380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12124 KB |
Output is correct |
2 |
Correct |
265 ms |
88624 KB |
Output is correct |
3 |
Correct |
231 ms |
88396 KB |
Output is correct |
4 |
Correct |
537 ms |
80720 KB |
Output is correct |
5 |
Correct |
225 ms |
87668 KB |
Output is correct |
6 |
Correct |
231 ms |
87560 KB |
Output is correct |
7 |
Correct |
221 ms |
80980 KB |
Output is correct |
8 |
Correct |
405 ms |
81236 KB |
Output is correct |
9 |
Correct |
325 ms |
80492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
12008 KB |
Output is correct |
2 |
Correct |
366 ms |
80888 KB |
Output is correct |
3 |
Correct |
977 ms |
80816 KB |
Output is correct |
4 |
Correct |
1037 ms |
80796 KB |
Output is correct |
5 |
Correct |
1165 ms |
80668 KB |
Output is correct |
6 |
Correct |
443 ms |
80832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
420 ms |
94256 KB |
Output is correct |
2 |
Correct |
406 ms |
94340 KB |
Output is correct |
3 |
Correct |
413 ms |
93764 KB |
Output is correct |
4 |
Correct |
433 ms |
93772 KB |
Output is correct |
5 |
Correct |
361 ms |
90552 KB |
Output is correct |
6 |
Correct |
357 ms |
90432 KB |
Output is correct |
7 |
Correct |
282 ms |
89140 KB |
Output is correct |
8 |
Correct |
241 ms |
88920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12124 KB |
Output is correct |
2 |
Correct |
4 ms |
12008 KB |
Output is correct |
3 |
Correct |
3 ms |
12124 KB |
Output is correct |
4 |
Correct |
3 ms |
12376 KB |
Output is correct |
5 |
Correct |
5 ms |
12124 KB |
Output is correct |
6 |
Correct |
3 ms |
12124 KB |
Output is correct |
7 |
Correct |
4 ms |
12124 KB |
Output is correct |
8 |
Correct |
3 ms |
12124 KB |
Output is correct |
9 |
Correct |
3 ms |
12124 KB |
Output is correct |
10 |
Correct |
4 ms |
12124 KB |
Output is correct |
11 |
Correct |
3 ms |
12120 KB |
Output is correct |
12 |
Correct |
3 ms |
12124 KB |
Output is correct |
13 |
Correct |
4 ms |
12376 KB |
Output is correct |
14 |
Correct |
4 ms |
12380 KB |
Output is correct |
15 |
Correct |
5 ms |
12380 KB |
Output is correct |
16 |
Correct |
4 ms |
12380 KB |
Output is correct |
17 |
Correct |
5 ms |
12380 KB |
Output is correct |
18 |
Correct |
4 ms |
12380 KB |
Output is correct |
19 |
Correct |
3 ms |
12380 KB |
Output is correct |
20 |
Correct |
4 ms |
12380 KB |
Output is correct |
21 |
Correct |
4 ms |
12380 KB |
Output is correct |
22 |
Correct |
4 ms |
12380 KB |
Output is correct |
23 |
Correct |
62 ms |
24408 KB |
Output is correct |
24 |
Correct |
66 ms |
24156 KB |
Output is correct |
25 |
Correct |
65 ms |
24412 KB |
Output is correct |
26 |
Correct |
133 ms |
23636 KB |
Output is correct |
27 |
Correct |
128 ms |
23584 KB |
Output is correct |
28 |
Correct |
126 ms |
23388 KB |
Output is correct |
29 |
Correct |
138 ms |
23136 KB |
Output is correct |
30 |
Correct |
160 ms |
23128 KB |
Output is correct |
31 |
Correct |
47 ms |
22996 KB |
Output is correct |
32 |
Correct |
35 ms |
25304 KB |
Output is correct |
33 |
Correct |
58 ms |
24152 KB |
Output is correct |
34 |
Correct |
62 ms |
24156 KB |
Output is correct |
35 |
Correct |
76 ms |
24152 KB |
Output is correct |
36 |
Correct |
108 ms |
24180 KB |
Output is correct |
37 |
Correct |
91 ms |
24184 KB |
Output is correct |
38 |
Correct |
94 ms |
24152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12124 KB |
Output is correct |
2 |
Correct |
4 ms |
12008 KB |
Output is correct |
3 |
Correct |
3 ms |
12124 KB |
Output is correct |
4 |
Correct |
3 ms |
12376 KB |
Output is correct |
5 |
Correct |
5 ms |
12124 KB |
Output is correct |
6 |
Correct |
3 ms |
12124 KB |
Output is correct |
7 |
Correct |
4 ms |
12124 KB |
Output is correct |
8 |
Correct |
3 ms |
12124 KB |
Output is correct |
9 |
Correct |
3 ms |
12124 KB |
Output is correct |
10 |
Correct |
4 ms |
12124 KB |
Output is correct |
11 |
Correct |
3 ms |
12120 KB |
Output is correct |
12 |
Correct |
3 ms |
12124 KB |
Output is correct |
13 |
Correct |
4 ms |
12376 KB |
Output is correct |
14 |
Correct |
4 ms |
12380 KB |
Output is correct |
15 |
Correct |
5 ms |
12380 KB |
Output is correct |
16 |
Correct |
4 ms |
12380 KB |
Output is correct |
17 |
Correct |
5 ms |
12380 KB |
Output is correct |
18 |
Correct |
4 ms |
12380 KB |
Output is correct |
19 |
Correct |
3 ms |
12380 KB |
Output is correct |
20 |
Correct |
4 ms |
12380 KB |
Output is correct |
21 |
Correct |
4 ms |
12380 KB |
Output is correct |
22 |
Correct |
4 ms |
12380 KB |
Output is correct |
23 |
Correct |
265 ms |
88624 KB |
Output is correct |
24 |
Correct |
231 ms |
88396 KB |
Output is correct |
25 |
Correct |
537 ms |
80720 KB |
Output is correct |
26 |
Correct |
225 ms |
87668 KB |
Output is correct |
27 |
Correct |
231 ms |
87560 KB |
Output is correct |
28 |
Correct |
221 ms |
80980 KB |
Output is correct |
29 |
Correct |
405 ms |
81236 KB |
Output is correct |
30 |
Correct |
325 ms |
80492 KB |
Output is correct |
31 |
Correct |
366 ms |
80888 KB |
Output is correct |
32 |
Correct |
977 ms |
80816 KB |
Output is correct |
33 |
Correct |
1037 ms |
80796 KB |
Output is correct |
34 |
Correct |
1165 ms |
80668 KB |
Output is correct |
35 |
Correct |
443 ms |
80832 KB |
Output is correct |
36 |
Correct |
420 ms |
94256 KB |
Output is correct |
37 |
Correct |
406 ms |
94340 KB |
Output is correct |
38 |
Correct |
413 ms |
93764 KB |
Output is correct |
39 |
Correct |
433 ms |
93772 KB |
Output is correct |
40 |
Correct |
361 ms |
90552 KB |
Output is correct |
41 |
Correct |
357 ms |
90432 KB |
Output is correct |
42 |
Correct |
282 ms |
89140 KB |
Output is correct |
43 |
Correct |
241 ms |
88920 KB |
Output is correct |
44 |
Correct |
62 ms |
24408 KB |
Output is correct |
45 |
Correct |
66 ms |
24156 KB |
Output is correct |
46 |
Correct |
65 ms |
24412 KB |
Output is correct |
47 |
Correct |
133 ms |
23636 KB |
Output is correct |
48 |
Correct |
128 ms |
23584 KB |
Output is correct |
49 |
Correct |
126 ms |
23388 KB |
Output is correct |
50 |
Correct |
138 ms |
23136 KB |
Output is correct |
51 |
Correct |
160 ms |
23128 KB |
Output is correct |
52 |
Correct |
47 ms |
22996 KB |
Output is correct |
53 |
Correct |
35 ms |
25304 KB |
Output is correct |
54 |
Correct |
58 ms |
24152 KB |
Output is correct |
55 |
Correct |
62 ms |
24156 KB |
Output is correct |
56 |
Correct |
76 ms |
24152 KB |
Output is correct |
57 |
Correct |
108 ms |
24180 KB |
Output is correct |
58 |
Correct |
91 ms |
24184 KB |
Output is correct |
59 |
Correct |
94 ms |
24152 KB |
Output is correct |
60 |
Correct |
663 ms |
88620 KB |
Output is correct |
61 |
Correct |
628 ms |
88656 KB |
Output is correct |
62 |
Correct |
689 ms |
88624 KB |
Output is correct |
63 |
Correct |
1173 ms |
81744 KB |
Output is correct |
64 |
Correct |
1216 ms |
81748 KB |
Output is correct |
65 |
Correct |
1242 ms |
81560 KB |
Output is correct |
66 |
Correct |
1144 ms |
80672 KB |
Output is correct |
67 |
Correct |
1157 ms |
80668 KB |
Output is correct |
68 |
Correct |
320 ms |
84080 KB |
Output is correct |
69 |
Correct |
223 ms |
97436 KB |
Output is correct |
70 |
Correct |
649 ms |
91020 KB |
Output is correct |
71 |
Correct |
664 ms |
91032 KB |
Output is correct |
72 |
Correct |
627 ms |
90116 KB |
Output is correct |
73 |
Correct |
894 ms |
90512 KB |
Output is correct |
74 |
Correct |
945 ms |
90572 KB |
Output is correct |
75 |
Correct |
922 ms |
90684 KB |
Output is correct |