#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e5 * 5 + 10;
int t[4 * N];
pair<int, int> pref_max[4 * N], pref_min[4 * N], suf_max[4 * N], suf_min[4 * N];
int n;
void update(int v, int l, int r, int pos, int val) {
if (l == r) {
t[v] = val;
pref_max[v] = {max(0, val), (val >= 0 ? l : -1)}, pref_min[v] = {min(0, val), (val <= 0 ? l : -1)};
suf_max[v] = {max(0, val), (val >= 0 ? l : n)}, suf_min[v] = {min(0, val), (val <= 0 ? l : n)};
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(v * 2, l, mid, pos, val);
else update(v * 2 + 1, mid + 1, r, pos, val);
t[v] = t[v * 2] + t[v * 2 + 1];
pref_max[v] = max(pref_max[v * 2], {t[v * 2] + pref_max[v * 2 + 1].first, pref_max[v * 2 + 1].second});
pref_min[v] = min(pref_min[v * 2], {t[v * 2] + pref_min[v * 2 + 1].first, pref_min[v * 2 + 1].second});
suf_max[v] = max(suf_max[v * 2 + 1], {t[v * 2 + 1] + suf_max[v * 2].first, suf_max[v * 2].second});
suf_min[v] = min(suf_min[v * 2 + 1], {t[v * 2 + 1] + suf_min[v * 2].first, suf_min[v * 2].second});
}
pair<int, int> get_max_pref(int v, int l, int r, int p) {
if (l > p)
return {-(int) 1e9, -1};
if (r <= p)
return pref_max[v];
int mid = (l + r) / 2;
if (mid >= p) return get_max_pref(v * 2, l, mid, p);
auto pr = get_max_pref(v * 2 + 1, mid + 1, r, p);
return max(get_max_pref(v * 2, l, mid, p), {t[v * 2] + pr.first, pr.second});
}
pair<int, int> get_min_pref(int v, int l, int r, int p) {
if (l > p)
return {(int) 1e9, -1};
if (r <= p)
return pref_min[v];
int mid = (l + r) / 2;
if (mid >= p) return get_min_pref(v * 2, l, mid, p);
auto pr = get_min_pref(v * 2 + 1, mid + 1, r, p);
return min(get_min_pref(v * 2, l, mid, p), {t[v * 2] + pr.first, pr.second});
}
pair<int, int> get_max_suf(int v, int l, int r, int p) {
if (r < p)
return {-(int) 1e9, -1};
if (l >= p)
return suf_max[v];
int mid = (l + r) / 2;
if (mid < p) return get_max_suf(v * 2 + 1, mid + 1, r, p);
auto pr = get_max_suf(v * 2, l, mid, p);
return max(get_max_suf(v * 2 + 1, mid + 1, r, p), {t[v * 2 + 1] + pr.first, pr.second});
}
pair<int, int> get_min_suf(int v, int l, int r, int p) {
if (r < p)
return {(int) 1e9, -1};
if (l >= p)
return suf_min[v];
int mid = (l + r) / 2;
if (mid < p) return get_min_suf(v * 2 + 1, mid + 1, r, p);
auto pr = get_min_suf(v * 2, l, mid, p);
return min(get_min_suf(v * 2 + 1, mid + 1, r, p), {t[v * 2 + 1] + pr.first, pr.second});
}
int get_sum(int v, int l, int r, int tl, int tr) {
if (l > tr || r < tl) return 0;
if (l >= tl && r <= tr)
return t[v];
int mid = (l + r) / 2;
return get_sum(v * 2, l, mid, tl, tr) + get_sum(v * 2 + 1, mid + 1, r, tl, tr);
}
int sequence(int nn, vector<int> a) {
n = nn;
set<int, greater<>> val;
map<int, vector<int>> pos;
for (int i = 0; i < n; i++) {
pos[a[i]].emplace_back(i);
val.insert(a[i]);
}
int l_max[n], l_min[n], r_max[n], r_min[n];
for (int i = 0; i < n; i++) {
l_max[i] = l_min[i] = r_max[i] = r_min[i] = i;
int c1 = 0, c2 = 0, c3 = 0, c4 = 0;
int big = 0, small = 0;
for (int j = i - 1; j >= 0; j--) {
small += (a[j] < a[i]), big += (a[j] > a[i]);
if (small - big > c1)
c1 = small - big, l_max[i] = j;
if (small - big < c2)
c2 = small - big, l_min[i] = j;
}
small = 0, big = 0;
for(int j = i + 1; j < n; j++){
small += (a[j] < a[i]), big += (a[j] > a[i]);
if (small - big > c3)
c3 = small - big, r_max[i] = j;
if (small - big < c4)
c4 = small - big, r_min[i] = j;
}
}
int l = 0, r = n + 1;
while (r - l > 1) {
int m = (l + r) / 2, C = 0;
for (int i = 0; i < n; i++) update(1, 0, n - 1, i, 1);
for (int x: val) {
for (int i: pos[x]) update(1, 0, n - 1, i, 0);
for (int i = 0; i + m - 1 < (int) pos[x].size(); i++) {
int L = pos[x][i], R = pos[x][i + m - 1];
int dif, sum, l1, l2;
int LL = L, RR = R;
for (int t1 = 0; t1 < 3; t1++) {
if (t1 == 0) L = l_min[LL];
else if (t1 == 1) L = l_max[LL];
else L = LL;
for (int t2 = 0; t2 < 3; t2++) {
if (t2 == 0) R = r_min[RR];
else if (t2 == 1)R = r_max[RR];
else R = RR;
dif = get_sum(1, 0, n - 1, L, R), sum = R - L + 1 - m;
l1 = (sum + dif) / 2, l2 = (sum - dif) / 2;
if (((L + R) / 2 >= L + l1 && (L + R) / 2 <= R - l2)
|| ((L + R + 1) / 2 >= L + l1 && (L + R + 1) / 2 <= R - l2)) {
C = 1;
break;
}
}
}
}
for (int i: pos[x]) update(1, 0, n - 1, i, -1);
}
if (C == 1) l = m;
else r = m;
}
return l;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 13 |
Incorrect |
25 ms |
8796 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Execution timed out |
2059 ms |
61524 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Execution timed out |
2049 ms |
14356 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2036 ms |
90364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 13 |
Incorrect |
25 ms |
8796 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 13 |
Incorrect |
25 ms |
8796 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
