Submission #1102385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102385		ioane	Nile (IOI24_nile)	C++17	38 / 100	63 ms	9432 KiB

nile

#include <bits/stdc++.h>
 
#define LL long long
#define PB push_back
#define MP make_pair
#define F first
#define S second

#define FF fflush(stdout)
#define d(C) C-'a'
 
const LL N = 100005;
const LL mod = 1000000007;
 
using namespace std;

int p[N], sz[N];

int get_p(int u){
    if (p[u] == u) return u;
    p[u] = get_p(p[u]);
    return p[u];
}

int merge(int u, int v){
    u = get_p(u);
    v = get_p(v);
    if (sz[u] < sz[v]) swap(u, v);
    p[v] = u;
    sz[u] += sz[v];
    return u;
}

std::vector<long long> calculate_costs(
    std::vector<int> W, std::vector<int> A, 
    std::vector<int> B, std::vector<int> E) {
    
    int n = W.size();
    int q = E.size();
    long long total_a = 0;
    
    for (int i = 0; i < n; ++i){
        p[i] = i;
        sz[i] = 1;
    }
    
    vector<pair<int, int> > v, diff;
    LL ans[n];
    int mn[n];
    for (int i = 0; i < n; ++i){
        v.PB(MP(W[i], A[i] - B[i]));
        total_a += A[i];
    }
    sort(v.begin(), v.end());
    
    for (int i = 1; i < n; ++i){
        diff.PB(MP(v[i].F - v[i-1].F, i));
        mn[i] = v[i].S;
        ans[i] = 0;
    }
    ans[0] = 0;
    mn[0] = v[0].S;
    
    sort(diff.begin(), diff.end());
    
    int diff_i = 0;
    
    vector<long long> result(q);
    
    LL ans_profit = 0;
    
    vector<pair<int, int> > queries;
    for (int i = 0; i < q; ++i){
        queries.PB(MP(E[i], i));
    }
    sort(queries.begin(), queries.end());
    
    for (int i_E = 0; i_E < q; ++i_E){
        int d = queries[i_E].F;
        
        while (diff_i < n-1 && diff[diff_i].F <= d){
            int ind = diff[diff_i].S;
            int u = get_p(ind-1);
            int v = get_p(ind);
            
            int new_mn = min(mn[u], mn[v]);
            
            if (sz[u] & 1) {ans_profit += mn[u]; ans[u] += mn[u];}
            if (sz[v] & 1) {ans_profit += mn[v]; ans[v] += mn[v];}
            LL new_ans = ans[u] + ans[v];
            if ((sz[u] + sz[v]) & 1) {ans_profit -= new_mn; new_ans -= new_mn;}
            
            int par = merge(u, v);
            ans[par] = new_ans;
            mn[par] = new_mn;
            
            diff_i++;
        }
        
        LL answ = total_a - ans_profit;
        result[queries[i_E].S] = answ;
    }
    
    return result;
}

//      IIIIIIIII      OOOOO             A          NN        N    EEEEEEEEEE
//          I         O     O           A A         N N       N    E
//          I        O       O         A   A        N  N      N    E
//          I        O       O        A     A       N   N     N    E
//          I        O       O       AAAAAAAAA      N    N    N    EEEEEEEE
//          I        O       O      A         A     N     N   N    E
//          I        O       O     A           A    N      N  N    E
//          I         O     O     A             A   N       N N    E
//      IIIIIIIII      OOOOO     A               A  N        NN    EEEEEEEEEE ___ KAPANADZE

• Subtask 0: 0 / 0
• Subtask 1: 6 / 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