Submission #1102385

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1102385	2024-10-18T03:40:33 Z	ioane	Nile (IOI24_nile)	C++17	38 / 100	63 ms	9432 KB

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 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	552 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct

Subtask #2
0.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	34 ms	6844 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	6852 KB	Output is correct
2	Correct	30 ms	6936 KB	Output is correct
3	Correct	35 ms	6852 KB	Output is correct
4	Correct	36 ms	6856 KB	Output is correct
5	Correct	35 ms	6956 KB	Output is correct
6	Correct	38 ms	6852 KB	Output is correct

Subtask #4
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	552 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Incorrect	2 ms	336 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	552 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Incorrect	34 ms	6844 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #6
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	6852 KB	Output is correct
2	Correct	30 ms	6936 KB	Output is correct
3	Correct	35 ms	6852 KB	Output is correct
4	Correct	36 ms	6856 KB	Output is correct
5	Correct	35 ms	6956 KB	Output is correct
6	Correct	38 ms	6852 KB	Output is correct
7	Correct	51 ms	9284 KB	Output is correct
8	Correct	52 ms	9284 KB	Output is correct
9	Correct	60 ms	9276 KB	Output is correct
10	Correct	58 ms	9276 KB	Output is correct
11	Correct	57 ms	9424 KB	Output is correct
12	Correct	60 ms	9276 KB	Output is correct
13	Correct	61 ms	9288 KB	Output is correct
14	Correct	56 ms	9424 KB	Output is correct
15	Correct	63 ms	9432 KB	Output is correct

Subtask #7
0.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	552 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Incorrect	34 ms	6844 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Submission #1102385

Compilation message