Submission #1177551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177551		TahirAliyev	Nile (IOI24_nile)	C++20	32 / 100	120 ms	43656 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;
int n;
array<int, 2> arr[MAX];
int ans = 0;
struct DSU{
    multiset<int> s[MAX];
    int par[MAX];
    void init(){
        for(int i = 0; i < n; i++){
            par[i] = -1;
            s[i] = {arr[i][1]};
            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){
        u = get(u), v = get(v);
        if(u == v) return 0;
        if(-par[u] < -par[v]) swap(u, v);
        if(s[u].size() & 1) ans -= *s[u].begin();
        if(s[v].size() & 1) ans -= *s[v].begin();
        par[u] += par[v];
        par[v] = u;
        for(int a : s[v]) s[u].insert(a);
        if(s[u].size() & 1) ans += *s[u].begin();
        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);
    vector<pii> v;
    for(int i = 0; i < n - 1; i++){
        v.push_back({arr[i + 1][0] - arr[i][0], i});
    }
    sort(all(v));
    reverse(all(v));
    vector<pii> Q;
    for(int i = 0; i < E.size(); i++) Q.push_back({E[i], i});
    dsu.init();
    sort(all(Q));
    vector<ll> res(Q.size(), 0);
    for(pii d : Q){
        while(v.size() && v.back().first <= d.first){
            dsu.unite(v.back().second, v.back().second + 1);
            v.pop_back();
        }
        res[d.second] = ans;
    }
    return res;
}

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