Submission #960316

#	Time	Username	Problem	Language	Result	Execution time	Memory
960316		alextodoran	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	295 ms	66640 KiB

constellation3

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;
const int M_MAX = 200000;
const int LOG_N = 18;

int N;
int A[N_MAX + 2];
int M;
struct Star {
    int x, y;
    int cost;
};
Star S[M_MAX + 2];

int L[N_MAX + 2], R[N_MAX + 2];

int st[N_MAX + 2], cnt;
void get_LR () {
    cnt = 0; st[0] = 0;
    for (int x = 1; x <= N; x++) {
        while (cnt > 0 && A[x] >= A[st[cnt]]) {
            cnt--;
        }
        L[x] = st[cnt] + 1;
        st[++cnt] = x;
    }
    cnt = 0; st[0] = N + 1;
    for (int x = N; x >= 1; x--) {
        while (cnt > 0 && A[x] >= A[st[cnt]]) {
            cnt--;
        }
        R[x] = st[cnt] - 1;
        st[++cnt] = x;
    }
}

int node[N_MAX + 2];
int parent[N_MAX + 2];
vector <int> sons[N_MAX + 2];
int anc[N_MAX + 2][LOG_N];
int root;

vector <int> stars[N_MAX + 2];

void get_tree () {
    iota(node + 1, node + N + 1, 1);
    for (int x = 1; x <= N; x++) {
        int l = L[x] - 1, r = R[x] + 1;
        if (1 <= l && r <= N && A[l] == A[r]) {
            node[r] = node[l];
        }
        if (A[x] == A[x - 1]) {
            node[x] = node[x - 1];
        }
    }
    for (int x = 1; x <= N; x++) {
        int l = L[x] - 1, r = R[x] + 1;
        parent[node[x]] = (A[l] <= A[r] ? node[l] : node[r]);
    }
    for (int u = 1; u <= N; u++) {
        if (node[u] == u) {
            sons[parent[u]].push_back(u);
            anc[u][0] = parent[u];
            if (parent[u] == 0) {
                root = u;
            }
        }
    }
    for (int k = 1; k < LOG_N; k++) {
        for (int u = 1; u <= N; u++) {
            anc[u][k] = anc[anc[u][k - 1]][k - 1];
        }
    }
    for (int i = 1; i <= M; i++) {
        int u = node[S[i].x];
        for (int k = LOG_N - 1; k >= 0; k--) {
            if (A[anc[u][k]] < S[i].y) {
                u = anc[u][k];
            }
        }
        stars[u].push_back(i);
    }
}

int eul[N_MAX + 2], eur[N_MAX + 2];
int curr;

void dfs (int u) {
    eul[u] = ++curr;
    for (int v : sons[u]) {
        dfs(v);
    }
    eur[u] = curr;
}

ll max_keep[N_MAX + 2];
ll sum_up[N_MAX + 2];
ll sum_sons_up[N_MAX + 2];

void update (ll Fen[], int pos, ll val) {
    for (int i = pos; i <= N; i += i & -i) {
        Fen[i] += val;
    }
}
void update (ll Fen[], int l, int r, ll val) {
    update(Fen, l, val);
    update(Fen, r + 1, -val);
}
ll query (ll Fen[], int pos) {
    ll sum = 0;
    for (int i = pos; i >= 1; i -= i & -i) {
        sum += Fen[i];
    }
    return sum;
}

ll chain_sum (int u) {
    return query(sum_sons_up, eul[u]) - query(sum_up, eul[u]);
}

void solve (int u) {
    ll sum_sons = 0;
    for (int v : sons[u]) {
        solve(v);
        sum_sons += max_keep[v];
    }
    update(sum_sons_up, eul[u], eur[u], sum_sons);
    max_keep[u] = sum_sons;
    for (int i : stars[u]) {
        max_keep[u] = max(max_keep[u], S[i].cost + chain_sum(node[S[i].x]));
    }
    update(sum_up, eul[u], eur[u], max_keep[u]);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    for (int x = 1; x <= N; x++) {
        cin >> A[x];
    }
    A[0] = A[N + 1] = N + 1;
    cin >> M;
    for (int i = 1; i <= M; i++) {
        cin >> S[i].x >> S[i].y >> S[i].cost;
    }
    get_LR();
    get_tree();
    dfs(root);
    solve(root);
    ll answer = 0;
    for (int i = 1; i <= M; i++) {
        answer += S[i].cost;
    }
    answer -= max_keep[root];
    cout << answer << "\n";

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65