Submission #1222940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222940		LucaIlie	Nile (IOI24_nile)	C++20	38 / 100	45 ms	9288 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];
int parent[MAX_N], sz[MAX_N];
long long sumB[MAX_N], minAB[MAX_N];
long long cost;

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 -= minAB[x];
    cost -= sumB[y];
    if (sz[y] % 2 == 1)
        cost -= minAB[y];


    sumB[x] += sumB[y];
    minAB[x] = min(minAB[x], minAB[y]);
    sz[x] += sz[y];
    parent[y] = x;

    cost += sumB[x];
    if (sz[x] % 2 == 1)
        cost += 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; 
    });

    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] = objects[i].a - objects[i].b;
        sz[i] = 1;
    }

    int j = 0;
    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);

            // printf("UNESC %d %d\n", updates[j].i, updates[j].i + 1);
            j++;
        }
        // printf("QUERY %d\n", queries[i].e);
        ans[queries[i].i] = cost;
    }

    return ans;
}

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