제출 #1166731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166731		Sang	나일강 (IOI24_nile)	C++20	38 / 100	78 ms	18612 KiB

nile

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

#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int n, a[N], b[N];
ii w[N];


struct DSU{
    vi lab, mi, s, L, R;
    int ans = 0;
    DSU(int n) : lab(n), mi(n), s(n), L(n), R(n) {};

    void make_set(int u){
        lab[u] = -1;
        s[u] = a[w[u].se] - b[w[u].se];
        mi[u] = INF;
        L[u] = R[u] = u;
    }

    int Find(int u){
        return lab[u] < 0 ? u : lab[u] = Find(lab[u]);
    }

    int get(int u){
        u = Find(u);
        if ((-lab[u])%2 == 0) return s[u];
        int x = min({a[w[L[u]].se] - b[w[L[u]].se], a[w[R[u]].se] - b[w[R[u]].se], mi[u]});
        return s[u] - x;
    }

    void active(int u){
        int v = Find(u);
        ans -= get(v);
        mi[v] = min(mi[v], a[w[u].se] - b[w[u].se]);
        ans += get(v);
    }

    void Union(int u, int v){
        if ((u = Find(u)) == (v = Find(v))) return;
        if (lab[u] < lab[v]) swap(u, v);
        ans -= get(u) + get(v);
        lab[u] += lab[v];
        lab[v] = u;
        mi[u] = min(mi[u], mi[v]);
        s[u] += s[v];
        L[u] = min(L[u], L[v]);
        R[u] = max(R[u], R[v]);
        ans += get(u);
    }
};

vector<int> calculate_costs(vector<int32_t> W, vector<int32_t> A, vector<int32_t> B, vector<int32_t> E){
    n = A.size();
    int s = 0;
    FOR (i, 1, n){
        w[i] = {W[i-1], i};
        a[i] = A[i-1];
        b[i] = B[i-1];
        s += a[i];
    }
    sort(w + 1, w + n + 1);
    vector<pii> edges;
    FOR (i, 1, n - 1) edges.pb({w[i+1].fi - w[i].fi, {i, i + 1}});
    DSU dsu(n + 5);
    FOR (i, 1, n) dsu.make_set(i);
    vector<ii> queries, nodes;
    FOR (i, 1, n){
        if (i == 1) nodes.pb({w[i+1].fi-w[i].fi, i});
        else if (i == n) nodes.pb({w[i].fi - w[i-1].fi, i});
        else
            nodes.pb({w[i+1].fi - w[i-1].fi, i});
    }
    FOR (i, 0, (int)E.size() - 1) queries.pb({E[i], i});
    sort(ALL(queries), greater<ii>());
    sort(ALL(edges), greater<pii>());
    sort(ALL(nodes), greater<ii>());
    vector<int> ans(E.size(), 0);
    while (!queries.empty()){
        while (!edges.empty() && edges.back().fi <= queries.back().fi){
            dsu.Union(edges.back().se.fi, edges.back().se.se);
            edges.pop_back();
        }
        while (!nodes.empty() && nodes.back().fi <= queries.back().fi){
            dsu.active(nodes.back().se);
            nodes.pop_back();
        }
        ans[queries.back().se] = s - dsu.ans;
        queries.pop_back();
    }
    return ans;
}

#ifdef _Pbrngw_
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    vi ans = calculate_costs({15, 12, 2, 10, 21}, {5, 4, 5, 6, 3}, {1, 2, 2, 3, 2}, {5, 9, 1});
    for (int &x : ans) cout << x << '\n';
    return 0;
}
#endif // _Pbrngw_

• 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