#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,sum;
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,sum=minr;
if (l < r) {
sl = new node(l, mid);
sr = new node(mid + 1, r);
}
}
void update(int i, int p) {
if (l == r) {
sum += p;
minl = 0;
minr = 0;
maxl = sum, maxr = sum;
}
else {
if (i <= mid)sl->update(i, p);
else sr->update(i, p);
sum = sl->sum + sr->sum;
minl = min(sl->minl, sl->sum + sr->minl);
minr = min(sr->minr, sr->sum + sl->minr);
maxl = max(sl->maxl, sl->sum + sr->maxl);
maxr = max(sr->maxr, sr->sum + sl->maxr);
}
}
int query1(int a, int b) {
if (a>r || b <l)return 0;
if (a <= l && b >= r)return sum;
if (a <= mid)return min(sl->query1(a, b), sl->query1(a, mid) + sr->minl);
if (b > 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 > r || b < l)return 0;
if (a <= l && b >= r)return sum;
if (a <= mid)return max(sl->query1(a, b), sl->query1(a, mid) + sr->maxl);
if (b > mid)return max(sr->query1(a, b), sr->query1(mid + 1, b) + sl->maxr);
return sl->query1(a, mid) + sr->query1(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()) {
pi p = { seg->query1(his[i][it1], his[i][it2 + 1]),seg->query2(his[i][it1],his[i][it2 + 1]) };
if (p.x+it1-it2-2 > 0 || p.y+it2+2-it1 < 0) {
it1++;
}
else {
it2++;
}
if (it1 > it2)it2++;
ans = max(ans, it2 - it1 + 1);
}
for (int a : his[i])seg->update(a, 1);
}
return ans;
}
Compilation message
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | while (it2+1 < his[i].size()) {
| ~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12120 KB |
Output is correct |
2 |
Correct |
3 ms |
12124 KB |
Output is correct |
3 |
Correct |
3 ms |
12164 KB |
Output is correct |
4 |
Incorrect |
3 ms |
12124 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12120 KB |
Output is correct |
2 |
Correct |
3 ms |
12124 KB |
Output is correct |
3 |
Correct |
3 ms |
12164 KB |
Output is correct |
4 |
Incorrect |
3 ms |
12124 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12120 KB |
Output is correct |
2 |
Execution timed out |
2043 ms |
91732 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12124 KB |
Output is correct |
2 |
Execution timed out |
2064 ms |
81584 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
404 ms |
97616 KB |
Output is correct |
2 |
Correct |
528 ms |
97772 KB |
Output is correct |
3 |
Execution timed out |
2043 ms |
96848 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12120 KB |
Output is correct |
2 |
Correct |
3 ms |
12124 KB |
Output is correct |
3 |
Correct |
3 ms |
12164 KB |
Output is correct |
4 |
Incorrect |
3 ms |
12124 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12120 KB |
Output is correct |
2 |
Correct |
3 ms |
12124 KB |
Output is correct |
3 |
Correct |
3 ms |
12164 KB |
Output is correct |
4 |
Incorrect |
3 ms |
12124 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |