Submission #1247947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247947		clementine	Nile (IOI24_nile)	C++20	51 / 100	74 ms	12220 KiB

nile

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

#pragma region Debugger
// Base printer for general types
template<typename T>
void __print(const T& x) {
    cerr << x;
}

// Specialized printer for string
void __print(const string& x) { cerr << '"' << x << '"'; }
void __print(const char* x)   { cerr << '"' << x << '"'; }
void __print(char x)          { cerr << '\'' << x << '\''; }
void __print(bool x)          { cerr << (x ? "true" : "false"); }

// Specialized printer for pair
template<typename T1, typename T2>
void __print(const pair<T1, T2>& p) {
    cerr << "(";
    __print(p.first);
    cerr << ", ";
    __print(p.second);
    cerr << ")";
}

// For containers: vector, set, map, etc. (but not string or pair)
template<typename T, typename = void>
struct is_container : false_type {};

template<typename T>
struct is_container<T, std::void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};

template<typename T>
typename enable_if<is_container<T>::value && !is_same<T, string>::value, void>::type
__print(const T& container) {
    cerr << "{";
    bool first = true;
    for (const auto& item : container) {
        if (!first) cerr << ", ";
        __print(item);
        first = false;
    }
    cerr << "}";
}

// Recursive variadic template debug printer
template<typename T>
void _debug_cerr(const char* name, T&& value) {
    cerr << name << ": ";
    __print(value);
    cerr << '\n';
}

template<typename T, typename... Args>
void _debug_cerr(const char* names, T&& value, Args&&... args) {
    const char* comma = strchr(names, ',');
    cerr.write(names, comma - names) << ": ";
    __print(value);
    cerr << ", ";
    _debug_cerr(comma + 1, forward<Args>(args)...);
}

// Macro interface
#define debug(...) _debug_cerr(#__VA_ARGS__, __VA_ARGS__)
#pragma endregion

vector<pair<int ,int>> w; // first int is size, second is the index it is 

// dsu node
struct Node
{
    int l, r; // r is the parent
    int size; 
    int min_even, min_odd;
    int min_safe_even, min_safe_odd;
    Node(int l, int r, int size, ll e, ll o, ll se, ll so) : l(l), r(r), size(size), min_even(e), min_odd(o), min_safe_even(se), min_safe_odd(so) {}
};
vector<Node> dsu_arr;



int find(int a)
{
    if(dsu_arr[a].r == a)return a;
    dsu_arr[a].r = find(dsu_arr[a].r);
    return dsu_arr[a].r;
}

vector<ll> calculate_costs(vector<int> W, vector<int> A,vector<int> B, vector<int> E) 
{
    int Q = (int)E.size();
    vector<ll> R(Q, 0);
    ll total_cost = 0;
    int n = (int) W.size();
    vector<pair<int, int>> e; // first is D[i], second is index
    vector<pair<int, int>> safe_dist(n, {-1, 0});
    vector<pair<int, int>> consec_dist(n - 1, {-1, 0}); // second is the index to the left ie dist i i+1 
    vector<int> diff(n, 0);
    for(int i = 0; i < n; i ++)
    {
        total_cost += A[i];
        w.push_back({W[i], i});
    }
    sort(w.begin(), w.end());
    for(int i = 0; i < n; i ++)
    {
        diff[w[i].second] = A[i] - B[i];
    }
    for(int i = 0 ; i< Q; i ++)
    {
        e.push_back({E[i], i});
    }
    sort(e.begin(), e.end());
    for(int i = 1; i < n-1; i ++)
    {
        safe_dist[i] = {w[i+1].first - w[i-1].first, i};
    }
    sort(safe_dist.begin(), safe_dist.end());
    int safe_dist_idx = 2;
    for(int i = 0; i < n-1; i ++)
    {
        consec_dist[i] = {w[i+1].first - w[i].first, i};
    }
    sort(consec_dist.begin(), consec_dist.end());
    int consec_dist_idx = 0;

    // initualize dsu
    for(int i = 0; i < n; i ++)
    {
        dsu_arr.push_back(Node(i, i, 1, diff[i], INT32_MAX, INT32_MAX, INT32_MAX));
    }
    //debug(total_cost);
    for(auto eval: e)
    {
        //debug(eval);
        
        // for each consecutive thing that is newly joined 
        while(consec_dist_idx < consec_dist.size() && consec_dist[consec_dist_idx].first <= eval.first)
        {
            int current_idx = consec_dist[consec_dist_idx].second;
            int parent = find(current_idx + 1);
            //debug(current_idx, parent);
            // update child stat to point to parent
            dsu_arr[current_idx].r = parent;
            // update the parent's stats
            // what happens to the mins?
            if(dsu_arr[current_idx].size % 2 == 1)
            {
                total_cost -= min(dsu_arr[current_idx].min_even, dsu_arr[current_idx].min_safe_odd);
            }
            if(dsu_arr[parent].size % 2 == 1)
            {
                total_cost -= min(dsu_arr[parent].min_even, dsu_arr[parent].min_safe_odd);
                //debug(dsu_arr[parent].min_even, dsu_arr[parent].min_safe_odd);
            }
            //debug(total_cost);
            if(dsu_arr[current_idx].size % 2 == 0)
            {
                //debug(dsu_arr[current_idx].size % 2);
                int new_min_even = min(dsu_arr[parent].min_even, dsu_arr[current_idx].min_even);
                int new_min_odd = min(dsu_arr[parent].min_odd, dsu_arr[current_idx].min_odd);
                int new_min_safe_even = min(dsu_arr[parent].min_safe_even, dsu_arr[current_idx].min_safe_even);
                int new_min_safe_odd = min(dsu_arr[parent].min_safe_odd, dsu_arr[current_idx].min_safe_odd);
                dsu_arr[parent].min_even = new_min_even;
                dsu_arr[parent].min_odd = new_min_odd;
                dsu_arr[parent].min_safe_even = new_min_safe_even;
                dsu_arr[parent].min_safe_odd = new_min_safe_odd;
            }
            else
            {
                //debug(dsu_arr[parent].min_safe_odd, dsu_arr[current_idx].min_even);
                int new_min_even = min(dsu_arr[parent].min_odd, dsu_arr[current_idx].min_even);
                int new_min_odd = min(dsu_arr[parent].min_even, dsu_arr[current_idx].min_odd);
                int new_min_safe_even = min(dsu_arr[parent].min_safe_odd, dsu_arr[current_idx].min_safe_even);
                int new_min_safe_odd = min(dsu_arr[parent].min_safe_even, dsu_arr[current_idx].min_safe_odd);
                dsu_arr[parent].min_even = new_min_even;
                dsu_arr[parent].min_odd = new_min_odd;
                dsu_arr[parent].min_safe_even = new_min_safe_even;
                dsu_arr[parent].min_safe_odd = new_min_safe_odd;
            }
            dsu_arr[parent].size += dsu_arr[current_idx].size; // updating paret size only now to not have problems
            if(dsu_arr[parent].size % 2 == 1)
            {
                total_cost += min(dsu_arr[parent].min_safe_odd, dsu_arr[parent].min_even);
            }
            //debug(dsu_arr[parent].min_even, dsu_arr[parent].min_safe_odd, total_cost);
            consec_dist_idx ++;
        }  
        
        // update safe distances 
        while(safe_dist_idx < safe_dist.size() && safe_dist[safe_dist_idx].first <= eval.first)
        {
            int current_idx = safe_dist[safe_dist_idx].second;
            int parent = find(current_idx);
            //debug(safe_dist[safe_dist_idx].first, current_idx, parent);
            if(dsu_arr[parent].size % 2 == 1 && (parent - current_idx) % 2 == 1) //if the current idx is on an odd spot then min odd must be updated to min(previous min, current idx difference)
            {
                //debug(dsu_arr[parent].size);
                if(dsu_arr[parent].min_safe_odd <= dsu_arr[parent].min_even)
                {
                    total_cost -= dsu_arr[parent].min_safe_odd;
                    total_cost += min(dsu_arr[parent].min_safe_odd, diff[current_idx]);
                }
                else
                {
                    total_cost -= dsu_arr[parent].min_even;
                    total_cost += min(dsu_arr[parent].min_even, diff[current_idx]);
                }
                dsu_arr[parent].min_safe_odd = min(dsu_arr[parent].min_safe_odd, diff[current_idx]);

            }
            else if((dsu_arr[parent].size % 2 == 1 && (parent - current_idx) % 2 == 0) || (dsu_arr[parent].size % 2 == 0 && (parent - current_idx) % 2 == 1))
            {
                dsu_arr[parent].min_safe_even = min(dsu_arr[parent].min_safe_even, diff[current_idx]); 
            }
            else if( dsu_arr[parent].size % 2 == 0 && (parent - current_idx) % 2 == 0)
            {
                dsu_arr[parent].min_safe_odd = min(dsu_arr[parent].min_safe_odd, diff[current_idx]);
            }
            safe_dist_idx ++;
        }
        
        R[eval.second] = total_cost;
    }
    return R;
}

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