This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 5e5 + 5, MIN_SCORE = -5e5 - 5, MAX_SCORE = 1e6 + 5;
int n;
int a[MAX_N];
int lo_sum[MAX_N], hi_sum[MAX_N], val_sum[MAX_N];
int lo_score[MAX_N], hi_score[MAX_N];
unordered_map<int, vector<int>> inds; // NOTE: we still must take from i + 1
void precomp(int val) {
inds.clear();
for (int i = 1; i <= n; i++) {
lo_sum[i] = lo_sum[i - 1] + (a[i] < val);
hi_sum[i] = hi_sum[i - 1] + (a[i] > val);
val_sum[i] = val_sum[i - 1] + (a[i] == val);
lo_score[i] = 2 * lo_sum[i] - i, hi_score[i] = 2 * hi_sum[i] - i;
inds[lo_score[i - 1]].push_back(i - 1);
if (i == n) inds[lo_score[i]].push_back(i);
// cout << i << ": " << lo_score[i] << " " << hi_score[i] << endl;
}
}
int st[5 * (MAX_SCORE - MIN_SCORE)];
void update(int i, int x, int u = 1, int lo = MIN_SCORE, int hi = MAX_SCORE) {
if (i < lo || i > hi) return;
if (lo == hi) { st[u] = max(st[u], x); return; }
int mid = floor((lo + hi) / (double) 2);
update(i, x, 2 * u, lo, mid), update(i, x, 2 * u + 1, mid + 1, hi);
st[u] = max(st[2 * u], st[2 * u + 1]);
}
int query(int l, int r, int u = 1, int lo = MIN_SCORE, int hi = MAX_SCORE) {
if (r < lo || l > hi) return 0;
if (l <= lo && hi <= r) return st[u];
int mid = floor((lo + hi) / (double) 2);
return max(query(l, r, 2 * u, lo, mid), query(l, r, 2 * u + 1, mid + 1, hi));
}
int solve_val(int val) {
// cout << "VALUE " << val << ": " << endl;
for (int u = 0; u < 5 * (MAX_SCORE - MIN_SCORE); u++) st[u] = 0;
precomp(val);
int ans = 0;
for (int x = MIN_SCORE; x <= MAX_SCORE; x++) {
if (inds.count(x) == 0) continue;
// cout << "SCORE " << x << ": ";
for (int y : inds[x]) {
// cout << y << " ";
update(hi_score[y], y);
}
for (int y : inds[x]) {
int resp = query(MIN_SCORE, hi_score[y]);
ans = max(ans, val_sum[resp] - val_sum[y]);
}
// cout << endl;
}
return ans;
}
int sequence(int tmp_n, vector<int> tmp_a) {
n = tmp_n;
for (int i = 0; i < n; i++) a[i + 1] = tmp_a[i];
int ans = 0;
for (int x : {1, 2, 3}) ans = max(ans, solve_val(x));
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |