Submission #1178698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178698		adaawf	Nile (IOI24_nile)	C++20	100 / 100	83 ms	16056 KiB

nile

#include <bits/stdc++.h>
using namespace std;
struct BOAT {
    long long int w, a, b;
} a[100005];
struct QUERY {
    int x, num;
} b[100005];
long long int p[100005], s[100005], res[100005], f[100005], ff[100005], g[100005], d = 0;
bool cmp(BOAT aa, BOAT bb) {
    return aa.w < bb.w;
}
bool cmp2(QUERY aa, QUERY bb) {
    return aa.x < bb.x;
}
int Find(int x) {
    if (x == p[x]) return x;
    return p[x] = Find(p[x]);
}
void Merge(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;
    p[y] = x;
    if (s[x] & 1) d -= min(f[x], g[x]);
    if (s[y] & 1) d -= min(f[y], g[y]);
    if (s[x] & 1) f[x] = min(f[x], ff[y]);
    else f[x] = min(f[x], f[y]);
    if (s[x] & 1) ff[x] = min(ff[x], f[y]);
    else ff[x] = min(ff[x], ff[y]);
    g[x] = min(g[x], g[y]);
    s[x] += s[y];
    if (s[x] & 1) d += min(f[x], g[x]);
}
vector<long long int> calculate_costs(vector<int> w, vector<int> x, vector<int> y, vector<int> e) {
    int n = w.size(), q = e.size();
    d = 0;
    for (int i = 1; i <= n; i++) {
        a[i] = {w[i - 1], x[i - 1], y[i - 1]};
        p[i] = i; res[i] = 0;
        s[i] = 1;
        d += x[i - 1];
    }
    for (int i = 1; i <= q; i++) {
        b[i] = {e[i - 1], i};
    }
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + q + 1, cmp2);
    vector<pair<int, pair<int, int>>> v;
    for (int i = 1; i <= n; i++) {
        f[i] = a[i].a - a[i].b;
        ff[i] = g[i] = 1e18;
    }
    for (int i = 2; i <= n; i++) {
        v.push_back({a[i].w - a[i - 1].w, {i, i - 1}});
        if (i != 1) v.push_back({a[i].w - a[i - 2].w, {i, i - 2}});
    }
    sort(v.begin(), v.end());
    int j = 0;
    for (int i = 1; i <= q; i++) {
        while (j < v.size() && v[j].first <= b[i].x) {
            if (v[j].second.first - v[j].second.second == 2) {
                int h = v[j].second.first - 1, k = Find(h);
                if (s[k] & 1) d -= min(f[k], g[k]);
                g[Find(h)] = min(g[Find(h)], a[h].a - a[h].b);
                if (s[k] & 1) d += min(f[k], g[k]);
            }
            else {
                Merge(v[j].second.first, v[j].second.second);
            }
            j++;
        }
        res[b[i].num] = d;
    }
    vector<long long int> ans;
    for (int i = 1; i <= q; i++) {
        ans.push_back(res[i]);
    }
    return ans;
}

• 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