제출 #1241277

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

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 2e5 + 5;

ll par[N], sum[N], len[N], mn[N];

int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    par[y] = x;
    sum[x] += sum[y];
    len[x] += len[y];
    mn[x] = min(mn[x], mn[y]);
}

vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
    int n = (int)w.size(), q = (int)e.size();
    vector<pll> at, qt;
    vector<ll> ans(q);
    for (int i = 0; i < n; i++) at.push_back({w[i], i});
    for (int i = 0; i < q; i++) qt.push_back({e[i], i});
    sort(at.begin(), at.end());
    sort(qt.begin(), qt.end());
    ll res = 0;
    for (int i = 0; i < n; i++) {
        par[i] = i, len[i] = 1;
        mn[i] = a[at[i].se] - b[at[i].se];
        sum[i] = b[at[i].se];
        res += a[at[i].se];
    }
    priority_queue<pll> pq;
    for (int i = 0; i < n - 1; i++) {
        pq.push({-(at[i + 1].fi - at[i].fi), i});
    }
    for (int i = 0; i < q; i++) {
        while (!pq.empty() and -pq.top().fi <= qt[i].fi) {
            int x = pq.top().se, y = x + 1;
            pq.pop();
            x = find(x), y = find(y);
            res -= sum[x] + sum[y];
            if (len[x] % 2) res -= mn[x];
            if (len[y] % 2) res -= mn[y];
            merge(x, y);
            x = find(x);
            res += sum[x];
            if (len[x] % 2) res += mn[x];
        }
        ans[qt[i].se] = res;
    }
    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