oj.uz

답안 #1102381

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1102381 2024-10-18T03:35:29 Z ioane 나일강 (IOI24_nile) C++17
0 / 100
 37 ms 6852 KB 
#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 mxmn = max(mn[u], mn[v]);
            ans_profit += (LL)mxmn;
            int new_ans = ans[u] + ans[v] + (LL)mxmn;
            int new_mn = min(mn[u], mn[v]);
            
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 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 Incorrect 2 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 6852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 6844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# 결과 실행 시간 메모리 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 Incorrect 2 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 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 Incorrect 2 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 6844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 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 Incorrect 2 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -