Submission #1177573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177573		TahirAliyev	Nile (IOI24_nile)	C++20	100 / 100	74 ms	9912 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long

const int MAX = 1e5 + 5, oo = 1e9 + 7;
int n;
array<int, 2> arr[MAX];
ll ans = 0;
struct DSU{
    int odd[MAX], even[MAX], mn[MAX];
    int par[MAX];
    void init(){
        for(int i = 0; i < n; i++){
            par[i] = -1;
            odd[i] = arr[i][1];
            even[i] = oo;
            mn[i] = oo;
            ans += arr[i][1];
        }
    }
    int get(int a){
        if(par[a] < 0) return a;
        return par[a] = get(par[a]);
    }
    bool unite(int u, int v){
        int i = v;
        u = get(u), v = get(v);
        if(u == v){
            if((-par[u]) & 1) ans -= min(mn[u], odd[u]);
            mn[u] = min(mn[u], arr[i][1]);
            if((-par[u]) & 1) ans += min(mn[u], odd[u]);
            return 0;
        }
        if((-par[u]) & 1) ans -= min(mn[u], odd[u]);
        if((-par[v]) & 1) ans -= min(mn[v], odd[v]);
        if((-par[u]) & 1){
            odd[u] = min(odd[u], even[v]);
            even[u] = min(even[u], odd[v]);
        }
        else{
            odd[u] = min(odd[u], odd[v]);
            even[u] = min(even[u], even[v]);
        }
        par[u] += par[v];
        par[v] = u;
        mn[u] = min(mn[u], mn[v]);
        if((-par[u]) & 1) ans += min(mn[u], odd[u]);
        return 1;
    }
};

DSU dsu;

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
    n = W.size();
    for(int i = 0; i < n; i++){
        arr[i] = {W[i], A[i] - B[i]};
        ans += B[i];
    }
    sort(arr, arr + n);
    dsu.init();
    vector<array<int, 3>> v;
    for(int i = 0; i < n - 1; i++){
        v.push_back({arr[i + 1][0] - arr[i][0], i, 1});
        if(i < n - 2) v.push_back({arr[i + 2][0] - arr[i][0], i + 1, 0});   
    }
    sort(all(v));
    reverse(all(v));
    vector<pii> Q;
    for(int i = 0; i < E.size(); i++) Q.push_back({E[i], i});
    sort(all(Q));
    vector<ll> res(Q.size(), 0);
    for(pii d : Q){
        while(v.size() && v.back()[0] <= d.first){
            if(v.back()[2]){
                dsu.unite(v.back()[1], v.back()[1] + 1);
                v.pop_back();
            }
            else{
                dsu.unite(v.back()[1], v.back()[1]);
                v.pop_back();
            }
        }
        res[d.second] = ans;
    }
    return res;
}

• 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