oj.uz

Submission #983377

# Submission time Handle Problem Language Result Execution time Memory
983377 2024-05-15T11:41:53 Z Ghetto Sequence (APIO23_sequence) C++17
12 / 100
 1292 ms 91280 KB 
#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;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 35416 KB Output is correct
2 Correct 64 ms 35460 KB Output is correct
3 Correct 67 ms 35488 KB Output is correct
4 Incorrect 93 ms 35416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 35416 KB Output is correct
2 Correct 64 ms 35460 KB Output is correct
3 Correct 67 ms 35488 KB Output is correct
4 Incorrect 93 ms 35416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 35416 KB Output is correct
2 Incorrect 1292 ms 90164 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 35460 KB Output is correct
2 Correct 1218 ms 90056 KB Output is correct
3 Correct 1226 ms 90284 KB Output is correct
4 Correct 1227 ms 91280 KB Output is correct
5 Correct 1274 ms 91140 KB Output is correct
6 Correct 1117 ms 91144 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1262 ms 90156 KB Output is correct
2 Correct 1267 ms 90160 KB Output is correct
3 Incorrect 1259 ms 90160 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 35416 KB Output is correct
2 Correct 64 ms 35460 KB Output is correct
3 Correct 67 ms 35488 KB Output is correct
4 Incorrect 93 ms 35416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 35416 KB Output is correct
2 Correct 64 ms 35460 KB Output is correct
3 Correct 67 ms 35488 KB Output is correct
4 Incorrect 93 ms 35416 KB Output isn't correct
5 Halted 0 ms 0 KB -