Submission #1124550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124550		caterpillow	Nile (IOI24_nile)	C++20	100 / 100	175 ms	25572 KiB

nile

#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll INF = 1e18;

int n;
struct Item {
    ll w, a, b;
    bool operator<(const Item& oth) const {
        return w < oth.w;
    }
};

struct Events {
    vector<int> joins, jumps, queries;
};

struct Range {
    int len, first;
    ll totb;
    array<ll, 2> min_jump_cost; // a - b
    array<ll, 2> min_skip_cost; // a - b

    ll get_cost() {
        if (len % 2 == 0) return totb;
        else {
            return totb + min(min_jump_cost[1], min_skip_cost[0]);
        }
    }

    Range operator+(const Range& oth) const {
        Range res;
        res.len = len + oth.len;
        res.first = first;
        res.totb = totb + oth.totb;
        if (len % 2 == 0) {
            res.min_jump_cost[0] = min(min_jump_cost[0], oth.min_jump_cost[0]);
            res.min_jump_cost[1] = min(min_jump_cost[1], oth.min_jump_cost[1]);
            res.min_skip_cost[0] = min(min_skip_cost[0], oth.min_skip_cost[0]);
            res.min_skip_cost[1] = min(min_skip_cost[1], oth.min_skip_cost[1]);
        } else {
            res.min_jump_cost[0] = min(min_jump_cost[0], oth.min_jump_cost[1]);
            res.min_jump_cost[1] = min(min_jump_cost[1], oth.min_jump_cost[0]);
            res.min_skip_cost[0] = min(min_skip_cost[0], oth.min_skip_cost[1]);
            res.min_skip_cost[1] = min(min_skip_cost[1], oth.min_skip_cost[0]);
        }
        return res;
    }
};

Range make_range(int i, ll b, ll a) {
    return {
        1, i,
        b,
        {INF, INF},
        {a - b, INF}
    };
}

struct DSU {
    vector<int> e;
    vector<Range> ranges;
    void init(int n) {
        e.resize(n, -1);
        ranges.resize(n);
    }
    int find(int x) {
        return e[x] < 0 ? x : e[x] = find(e[x]);   
    }
    Range& get(int x) {
        return ranges[find(x)];
    }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        assert(x != y);
        ranges[x] = ranges[x] + ranges[y];
        e[y] = x;
        return true;
    }
};

vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
    n = size(w);
    vector<Item> items(n);
    for (int i = 0; i < n; i++) {
        items[i] = {w[i], a[i], b[i]};
    }
    sort(items.begin(), items.end());
    
    map<ll, Events> evs;
    for (int i = 0; i < n - 1; i++) {
        evs[items[i + 1].w - items[i].w].joins.push_back(i);
    }
    for (int i = 1; i < n - 1; i++) {
        evs[items[i + 1].w - items[i - 1].w].jumps.push_back(i);
    }
    for (int i = 0; i < e.size(); i++) {
        evs[e[i]].queries.push_back(i);
    }

    DSU dsu;
    dsu.init(n);
    for (int i = 0; i < n; i++) dsu.ranges[i] = make_range(i, items[i].b, items[i].a);

    ll ans = accumulate(a.begin(), a.end(), 0ll);

    vector<ll> out(e.size());

    for (auto& [curd, events] : evs) {
        for (int i : events.joins) {
            ans -= dsu.get(i).get_cost();
            ans -= dsu.get(i + 1).get_cost();
            dsu.unite(i, i + 1);
            ans += dsu.get(i).get_cost();
        }
        for (int i : events.jumps) {
            Range& obj = dsu.get(i);
            ans -= obj.get_cost();

            int j = i - obj.first;
            obj.min_jump_cost[j % 2] = min(obj.min_jump_cost[j % 2], items[i].a - items[i].b);

            ans += obj.get_cost();
        }
        for (int i : events.queries) {
            out[i] = ans;
        }
    }

    return out;
}

• 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