Submission #1099755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099755		model_code	Nile (IOI24_nile)	C++17	100 / 100	86 ms	17860 KiB

nile

// correct/betatester_solution.cpp

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;


#define rep(i, a, b) for(int i = (a); i < (b); ++ i)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pb push_back

const int maxn = 2e5 + 100;
const int inf = 1e9 + 100;

ll cost = 0;

int dsu[maxn];
int sz[maxn];
int mn[maxn][3];

int a[maxn];
int c[maxn];

int root(int v){
    if(dsu[v] == v) return v;
    return dsu[v] = root(dsu[v]);
}

inline int Calc(int v){
    assert(v == root(v));
    return ((sz[v] & 1) ? min(mn[v][2], mn[v][v & 1]) : 0);
}

void Vol(int i){
    assert(root(i) == root(i + 1) && root(i) == root(i - 1));
    int v = root(i);
    cost -= Calc(v);
    mn[v][2] = min(mn[v][2], c[i]);
    cost += Calc(v);
}

void Union(int v, int u){
    v = root(v);
    u = root(u);
    assert(v != u);
    if(v > u) swap(v, u);
    cost -= Calc(v);
    cost -= Calc(u);
    dsu[u] = v;
    sz[v] += sz[u];
    rep(i, 0, 3){
        mn[v][i] = min(mn[v][i], mn[u][i]);
    }
    cost += Calc(v);
}

vector<long long>calculate_costs(vector<int>W, vector<int>A, vector<int>B, vector<int>E) {
    vector<ll> ans(SZ(E));
	int n = SZ(W);
	ll s = 0;
	for(int i : B) s += i;
	vector<pii> vec(n);
	rep(i, 0, n){
		vec[i] = {W[i], A[i] - B[i]};
	}
	sort(all(vec));
	
	rep(i, 0, n){
		a[i] = vec[i].F;
		c[i] = vec[i].S;
        assert(c[i] < inf);
        assert(c[i] >= 0);
	}

    rep(i, 0, n){
        dsu[i] = i;
        sz[i] = 1;
        rep(j, 0, 3) mn[i][j] = inf;
        mn[i][i & 1] = c[i];
        cost += Calc(i);
    }

    vector<pair<int, pii> > sonic;

    rep(i, 1, n){
        sonic.pb({a[i] - a[i - 1], {0, i}});
    }
    rep(i, 1, n - 1){
        sonic.pb({a[i + 1] - a[i - 1], {1, i}});
    }
    rep(i, 0, SZ(E)){
        sonic.pb({E[i], {2, i}});
    }
    
    sort(all(sonic));

    for(auto x : sonic){
        int t = x.S.F;
        int i = x.S.S;
        if(t == 0){
            Union(i, i - 1);
        }
        else if(t == 1){
            Vol(i);
        }
        else{
            ans[i] = s + cost;
        }
    }
	
    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