Submission #1247284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247284		colossal_pepe	Nile (IOI24_nile)	C++20	100 / 100	77 ms	16056 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = 1e12;

int n, q;
vector<pair<int, int>> queries;
vector<int> idx, w;
vector<ll> a, b;
vector<tuple<int, int, int>> edges;
ll ans;

struct DSU {
    struct Node {
        int e;
        ll tot, tot_b, l, ae, ao, be, bo;
        Node() { }
        Node(int i) {
            e = -1;
            tot = a[idx[i]];
            tot_b = b[idx[i]];
            l = i;
            if (i % 2) ae = INF, ao = a[idx[i]] - b[idx[i]];
            else ae = a[idx[i]] - b[idx[i]], ao = INF;
            be = bo = INF;
        }
    };
    vector<Node> t;
    DSU() {
        t.resize(n);
        for (int i = 0; i < n; i++) {
            t[i] = Node(i);
            ans += t[i].tot;
        }
    }
    int find(int x) {
        return (t[x].e < 0 ? x : t[x].e = find(t[x].e));
    }
    void updateTotal(int x) {
        ans -= t[x].tot;
        if (t[x].e % 2) t[x].tot = t[x].tot_b + (t[x].l % 2 ? min(t[x].ao, t[x].be) : min(t[x].ae, t[x].bo));
        else t[x].tot = t[x].tot_b;
        ans += t[x].tot;
    }
    void mergeFar(int i) {
        i++;
        int x = find(i);
        if (i % 2) t[x].bo = min(t[x].bo, a[idx[i]] - b[idx[i]]);
        else t[x].be = min(t[x].be, a[idx[i]] - b[idx[i]]);
        updateTotal(x);
    }
    void mergeClose(int i) {
        int x = find(i), y = find(i + 1);
        if (-t[x].e < -t[y].e) swap(x, y);
        ans -= t[y].tot;
        t[x].tot_b += t[y].tot_b;
        t[x].l = min(t[x].l, t[y].l);
        t[x].ae = min(t[x].ae, t[y].ae);
        t[x].ao = min(t[x].ao, t[y].ao);
        t[x].be = min(t[x].be, t[y].be);
        t[x].bo = min(t[x].bo, t[y].bo);
        t[x].e += t[y].e, t[y].e = x;
        updateTotal(x);
    }
};

void prep() {
    idx.resize(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) {
        return w[i] < w[j];
    });
}

void makeEdges() {
    for (int i = 0; i + 1 < n; i++) {
        edges.emplace_back(w[idx[i + 1]] - w[idx[i]], i + 1, i);
        if (i + 2 < n) edges.emplace_back(w[idx[i + 2]] - w[idx[i]], i + 2, i);
    }
    sort(edges.rbegin(), edges.rend());
}


vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {

    n = (int)W.size();
    w = W;
    a.assign(A.begin(), A.end());
    b.assign(B.begin(), B.end());
    prep();

    DSU dsu = DSU();

    makeEdges();

    q = (int)E.size();
    queries.resize(q);
    for (int i = 0; i < q; i++) {
        queries[i] = make_pair(E[i], i);
    }
    sort(queries.begin(), queries.end());

    vector<ll> ret(q);
    for (auto [d, qi] : queries) {
        while (not edges.empty() and get<0>(edges.back()) <= d) {
            auto [_, j, i] = edges.back();
            edges.pop_back();
            if (i == j - 1) dsu.mergeClose(i);
            else dsu.mergeFar(i);
        }
        ret[qi] = ans;
    }
    return ret;
}

• 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