Submission #1208761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208761		vanea	Nile (IOI24_nile)	C++20	0 / 100	43 ms	16124 KiB

nile

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

const int mxN = 1e5+10;
const ll INF = 1e18;

ll ans = 0;

ll p[mxN], mn_idx[mxN], c[mxN], mn_even[mxN], mn_odd[mxN], mn_idc[mxN];

int get(int x) {
    return p[x] < 0 ? x : p[x] = get(p[x]);
}

void uni(int a, int b) {
    int k = abs(a-b);
    a = get(a); b = get(b);
    if(a == b) {
        if(k == 2) {
            int idx = a+1;
            if(c[idx] < mn_idc[a]) {
                if(-p[a] & 1) {
                    if(mn_idx[a] & 1) {
                        ans -= min(mn_idc[a], mn_odd[a]);
                    }
                    else {
                        ans -= min(mn_idc[a], mn_even[a]);
                    }
                    ans += c[idx];
                }
                mn_idc[a] = c[idx];
            }
        }
        return ;
    }
    if(-p[a] & 1) {
        if(mn_idx[a] & 1) {
            ans -= min(mn_idc[a], mn_odd[a]);
        }
        else {
            ans -= min(mn_idc[a], mn_even[a]);
        }
    }
    if(-p[b] & 1) {
        if(mn_idx[b] & 1) {
            ans -= min(mn_idc[a], mn_odd[b]);
        }
        else {
            ans -= min(mn_idc[a], mn_even[b]);
        }
    }
    if(k == 2) {
        int idx = a+1;
        mn_idc[a] = min(mn_idc[a], c[idx]);
    }
    p[a] += p[b];
    p[b] = a;
    mn_idx[a] = min(mn_idx[a], mn_idx[b]);
    mn_even[a] = min(mn_even[a], mn_even[b]);
    mn_odd[a] = min(mn_odd[a], mn_odd[b]);
    mn_idc[a] = min(mn_idc[a], mn_idc[b]);
    if(-p[a] & 1) {
        if(mn_idx[a] & 1) {
            ans += min(mn_idc[a], mn_odd[a]);
        }
        else {
            ans += min(mn_even[a], mn_idc[a]);
        }
    }
}

vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e1) {
    int n = w.size(), q = e1.size();
    vector<array<ll, 3>> v(n);
    vector<array<int, 2>> e(q);
    for(int i = 0; i < n; i++) {
        v[i][0] = w[i];
    }
    for(int i = 0; i < n; i++) {
        v[i][1] = a[i];
    }
    for(int i = 0; i < n; i++) {
        v[i][2] = b[i];
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < n; i++) {
        p[i] = -1;
        mn_idx[i] = i;
        mn_even[i] = mn_odd[i] = INF;
        mn_idc[i] = INF;
        c[i] = v[i][1]-v[i][2];
        if(i & 1) mn_odd[i] = c[i];
        else mn_even[i] = c[i];
        ans += v[i][1];
    }
    for(int i = 0; i < q; i++) {
        e[i][0] = e1[i];
        e[i][1] = i;
    }
    sort(e.begin(), e.end());
    vector<array<ll, 3>> pairs;
    for(int i = 0; i < n; i++) {
        pairs.push_back({v[i+1][0]-v[i][0], i, i+1});
        if(i+2 < n) {
            pairs.push_back({v[i+2][0]-v[i][0], i, i+2});
        }
    }
    sort(pairs.begin(), pairs.end());
    vector<ll> res(q);
    int last = 0;
    for(int i = 0; i < q; i++) {
        while(last < pairs.size() && pairs[last][0] <= e[i][0]) {
            uni(pairs[last][1], pairs[last][2]);
            ++last;
        }
        res[e[i][1]] = ans;
    }
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18