Submission #1235415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235415		hugo_pm	Nile (IOI24_nile)	C++20	100 / 100	93 ms	27412 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = signed;
constexpr int INF = 2e18;
struct Query {
    int dis, id_qry;
    auto operator<=>(const Query&) const = default;
};
struct Artifact {
    int weight, value;
    auto operator<=>(const Artifact&) const = default;
};

struct Interval {
    int sum_values = 0, cnt_arts = 0;
    int min_even = INF, min_odd = INF, min_skipped = INF;
    int compute() {
        if (cnt_arts % 2 == 0)
            return sum_values;
        else
            return sum_values - min(min_even, min_skipped);
    }
    static Interval singleton(int value) {
        return {value, 1, value, INF, INF};
    }
};

Interval combine(Interval I, Interval J) {
    if (I.cnt_arts % 2)
        swap(J.min_even, J.min_odd);
    return {
        I.sum_values + J.sum_values,
        I.cnt_arts + J.cnt_arts,
        min(I.min_even, J.min_even),
        min(I.min_odd, J.min_odd),
        min(I.min_skipped, J.min_skipped)
    };
}

struct UF { // path compression only
    vector<int> repr;
    vector<Interval> info;
    int cur_answer = 0;
    UF(const vector<Artifact> &arts) {
        repr.resize(arts.size());
        iota(repr.begin(), repr.end(), 0);
        for (auto &art : arts)
            info.push_back(Interval::singleton(art.value));
    }
    int find(int x) {
        if (x != repr[x]) repr[x] = find(repr[x]);
        return repr[x];
    }
    void merge(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        assert(x < y);
        cur_answer -= info[x].compute() + info[y].compute();
        info[x] = combine(info[x], info[y]);
        cur_answer += info[x].compute();
        repr[y] = x;
    }
};

enum EventType { MERGE_ONE, MERGE_TWO, QUERY };
struct Event {
    int dis; EventType mode; int mode_arg; // {i, i+1}, {i, i+2} or id_qry
    auto operator<=>(const Event&) const = default;
};

vector<int> solve(vector<Artifact> arts, vector<Query> queries) {
    vector<int> answer(queries.size(), 0);
    sort(arts.begin(), arts.end());
    int nb_arts = arts.size();
    vector<Event> events;
    for (int i = 0; i < nb_arts-1; ++i) {
        auto &cur = arts[i], &nxt1 = arts[i+1];
        events.push_back({nxt1.weight - cur.weight, MERGE_ONE, i});
        if (i < nb_arts-2) {
            auto &nxt2 = arts[i+2];
            events.push_back({nxt2.weight - cur.weight, MERGE_TWO, i});
        }
    }
    for (auto &[dis, id_qry] : queries)
        events.push_back({dis, QUERY, id_qry});
    sort(events.begin(), events.end());

    UF uf(arts);
    for (auto &[dis, ev_typ, ev_arg] : events) {
        if (ev_typ == MERGE_ONE) {
            uf.merge(ev_arg, ev_arg+1);
        } else if (ev_typ == MERGE_TWO) {
            int jumped_over = ev_arg+1; // arg->arg+2
            auto &itv = uf.info[uf.find(jumped_over)];
            uf.cur_answer -= itv.compute();
            itv.min_skipped = min(itv.min_skipped, arts[jumped_over].value);
            uf.cur_answer += itv.compute();
        } else {
            assert(ev_typ == QUERY);
            answer[ev_arg] = uf.cur_answer;
        }
    }
    return answer;
}

vector<int> calculate_costs(vector<i32> W, vector<i32> A, vector<i32> B, vector<i32> E) {
    int nb_artifacts = W.size(), nb_queries = E.size();
    vector<Artifact> artifacts;
    for (int i = 0; i < nb_artifacts; ++i) {
        artifacts.push_back({W[i], A[i] - B[i]});
    }
    vector<Query> queries;
    for (int i = 0; i < nb_queries; ++i) {
        queries.push_back({E[i], i});
    }
    vector<int> answer = solve(artifacts, queries);
    int sum_A = accumulate(A.begin(), A.end(), 0ll);
    for (int &x : answer) {
        x = sum_A - x;
    }
    return answer;
}

• 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