# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
854460 |
2023-09-27T17:02:10 Z |
dxz05 |
Sequence (APIO23_sequence) |
C++17 |
|
1832 ms |
76064 KB |
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct SegmentTree{
struct node{
T sum;
T Min;
T Max;
T lazy;
bool isUpdated;
node(){
sum = Min = Max = 0;
lazy = 0;
isUpdated = false;
};
node(T x){
sum = Min = Max = x;
lazy = 0;
isUpdated = false;
}
};
vector<node> tree;
node neutral_element;
inline void combine(node &par, node lf, node rg){
par.sum = lf.sum + rg.sum;
par.Min = min(lf.Min, rg.Min);
par.Max = max(lf.Max, rg.Max);
}
int _begin, _end;
inline void init(int n){
_begin = 0;
_end = n - 1;
neutral_element.Min = 2 * n;
neutral_element.Max = -2 * n;
tree.resize(n * 4 + 5);
}
inline void upd(int v, int tl, int tr, T lazy){
tree[v].sum += lazy * (tr - tl + 1);
tree[v].Min += lazy;
tree[v].Max += lazy;
tree[v].isUpdated = true;
tree[v].lazy += lazy;
}
inline void push(int v, int tl, int tr){
if (tl == tr || !tree[v].isUpdated) return;
int tm = (tl + tr) >> 1;
upd(v << 1, tl, tm, tree[v].lazy);
upd(v << 1 | 1, tm + 1, tr, tree[v].lazy);
tree[v].lazy = 0;
tree[v].isUpdated = false;
}
inline void update(int v, int tl, int tr, int l, int r, T val){
push(v, tl, tr);
if (l <= tl && tr <= r){
upd(v, tl, tr, val);
return;
}
if (tl > r || tr < l) return;
int tm = (tl + tr) >> 1;
update(v << 1, tl, tm, l, r, val);
update(v << 1 | 1, tm + 1, tr, l, r, val);
combine(tree[v], tree[v << 1], tree[v << 1 | 1]);
}
inline void update(int l, int r, T val){
update(1, _begin, _end, l, r, val);
}
inline node get(int v, int tl, int tr, int l, int r){
push(v, tl, tr);
if (l <= tl && tr <= r) return tree[v];
if (tl > r || tr < l) return neutral_element;
int tm = (tl + tr) >> 1;
node res;
combine(res, get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
return res;
}
inline node get(int l, int r){
return get(1, _begin, _end, l, r);
}
inline int get(int i){
return get(i, i).sum;
}
};
int sequence(int N, std::vector<int> A) {
A.insert(A.begin(), 0);
vector<vector<int>> pos(N + 1);
for (int i = 1; i <= N; i++){
pos[A[i]].push_back(i);
}
int ans = 1;
int t = 0;
for (int i = 1; i <= N; i++){
if (i == 1 || A[i] == A[i - 1]){
t++;
} else {
t = 1;
}
ans = max(ans, t);
}
SegmentTree<int> st;
st.init(N + 1);
for (int i = 1; i <= N; i++){
st.update(i, N, 1);
}
for (int x = 1; x <= N; x++){
if (pos[x].empty()) continue;
for (int i : pos[x]){ // making 0
st.update(i, N, -1);
}
{
int i = pos[x].front(), j = pos[x].back();
int f = pos[x].size();
int sum = st.get(j) - st.get(i - 1);
if (abs(sum) <= f) ans = max(ans, f);
int l1 = st.get(i) - st.get(0, i).Max;
int r1 = st.get(i) - st.get(0, i).Min;
int l2 = st.get(j, N).Min - st.get(j);
int r2 = st.get(j, N).Max - st.get(j);
l1 = min(l1, 0), l2 = min(l2, 0);
r1 = max(r1, 0), r2 = max(r2, 0);
int need;
if (sum < -f) {
need = -f - sum;
} else {
need = f - sum;
}
if (l1 + l2 <= need && need <= r1 + r2) ans = max(ans, f);
}
for (int i : pos[x]){ // making -1
st.update(i, N, -1);
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1150 ms |
69648 KB |
Output is correct |
3 |
Correct |
1176 ms |
68780 KB |
Output is correct |
4 |
Correct |
423 ms |
58796 KB |
Output is correct |
5 |
Correct |
1086 ms |
69296 KB |
Output is correct |
6 |
Correct |
1074 ms |
67680 KB |
Output is correct |
7 |
Correct |
427 ms |
59092 KB |
Output is correct |
8 |
Correct |
443 ms |
60592 KB |
Output is correct |
9 |
Correct |
431 ms |
60336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
438 ms |
60972 KB |
Output is correct |
3 |
Correct |
446 ms |
60844 KB |
Output is correct |
4 |
Correct |
441 ms |
59820 KB |
Output is correct |
5 |
Correct |
480 ms |
62772 KB |
Output is correct |
6 |
Incorrect |
433 ms |
60872 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1830 ms |
74196 KB |
Output is correct |
2 |
Correct |
1832 ms |
76064 KB |
Output is correct |
3 |
Correct |
1767 ms |
73720 KB |
Output is correct |
4 |
Correct |
1780 ms |
73624 KB |
Output is correct |
5 |
Correct |
1438 ms |
70324 KB |
Output is correct |
6 |
Correct |
1426 ms |
70728 KB |
Output is correct |
7 |
Correct |
1193 ms |
69168 KB |
Output is correct |
8 |
Correct |
1177 ms |
69960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |