Submission #1222975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222975		LucaIlie	Nile (IOI24_nile)	C++20	100 / 100	62 ms	11336 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;

struct object {
    int w, a, b;
};

struct query {
    int e, i;
};

struct update {
    int d, i;
};

const int MAX_N = 1e5;
object objects[MAX_N];
query queries[MAX_N];
update updates[MAX_N];
update updates2[MAX_N];
int parent[MAX_N], sz[MAX_N], lft[MAX_N], rght[MAX_N];
long long sumB[MAX_N];
int minAB[MAX_N], minAB0[MAX_N], minAB1[MAX_N];
long long cost;

int ab(int i) {
    return objects[i].a - objects[i].b;
}

int findParent(int x) {
    if (parent[x] != x)
        parent[x] = findParent(parent[x]);
    return parent[x];
}

void unionn(int x, int y) {
    x = findParent(x);
    y = findParent(y);

    cost -= sumB[x];
    if (sz[x] % 2 == 1)
        cost -= min(minAB0[x], minAB[x]);
    cost -= sumB[y];
    if (sz[y] % 2 == 1)
        cost -= min(minAB0[y], minAB[y]);

    sumB[x] += sumB[y];
    minAB[x] = min(minAB[x], minAB[y]);
    if (sz[x] % 2 == 1) {
        minAB0[x] = min(minAB0[x], minAB1[y]);
        minAB1[x] = min(minAB1[x], minAB0[y]);
    } else {
        minAB0[x] = min(minAB0[x], minAB0[y]);
        minAB1[x] = min(minAB1[x], minAB1[y]);
    }
    sz[x] += sz[y];
    parent[y] = x;
    rght[x] = max(rght[x], rght[y]);
    lft[x] = min(lft[x], lft[y]);

    cost += sumB[x];
    if (sz[x] % 2 == 1)
        cost += min(minAB0[x], minAB[x]);
}

vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
    int n = w.size();
    int q = e.size();
    vector<long long> ans(q);

    for (int i = 0; i < n; i++) 
        objects[i] = {w[i], a[i], b[i]};
    for (int i = 0; i < q; i++) 
        queries[i] = {e[i], i};

    sort(objects, objects + n, [](object x, object y) {
        return x.w < y.w;
    });
    sort(queries, queries + q, [](query x, query y) {
        return x.e < y.e; 
    });

    for (int i = 0; i < n - 1; i++) 
        updates[i] = {objects[i + 1].w - objects[i].w, i};
    sort(updates, updates + n - 1, [](update x, update y) {
        return x.d < y.d; 
    });

    for (int i = 1; i < n - 1; i++) 
        updates2[i] = {objects[i + 1].w - objects[i - 1].w, i};
    sort(updates2 + 1, updates2 + n - 1, [](update x, update y) {
        return x.d < y.d; 
    });

    cost = 0;
    for (int i = 0; i < n; i++)
        cost += objects[i].a;

    for (int i = 0; i < n; i++) {
        parent[i] = i;
        sumB[i] = objects[i].b;
        minAB[i] = 1e9;
        minAB0[i] = objects[i].a - objects[i].b;
        minAB1[i] = 1e9;
        lft[i] = rght[i] = i;
        sz[i] = 1;
    }

    int j = 0, l = 1;
    for (int i = 0; i < q; i++) {
        while (j < n - 1 && updates[j].d <= queries[i].e) {
            unionn(updates[j].i, updates[j].i + 1);
            j++;
        }
        while (l < n - 1 && updates2[l].d <= queries[i].e) {
            int p = findParent(updates2[l].i);
            if (sz[p] % 2 == 1)
                cost -= min(minAB0[p], minAB[p]); 
            minAB[p] = min(minAB[p], ab(updates2[l].i));
            if (sz[p] % 2 == 1)
                cost += min(minAB0[p], minAB[p]); 
            l++;
        }
        // printf("QUERY %d\n", queries[i].e);
        ans[queries[i].i] = cost;
    }

    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18