제출 #983377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983377		Ghetto	서열 (APIO23_sequence)	C++17	12 / 100	1292 ms	91280 KiB

sequence

#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 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 12 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18