oj.uz

답안 #1105443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1105443 2024-10-26T12:14:40 Z LaMatematica14 나일강 (IOI24_nile) C++17
32 / 100
 93 ms 26100 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> par(1e6);
int fr(int a) {
    if (a == par[a]) return a;
    return par[a] = fr(par[a]);
}

void unite(int a, int b) {
    if (fr(a) == fr(b)) return;
    par[par[a]] = b;
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int N = W.size();
    vector<array<long long, 3>> stt(N); 
    for (int i = 0; i < N; i++) stt[i] = {W[i], B[i], A[i]-B[i]};
    sort(stt.begin(), stt.end());
    
    int Q = E.size();
    par.resize(N); iota(par.begin(), par.end(), 0);
    vector<array<long long, 3>> od;
    for (int i = 0; i < Q; i++) od.push_back({E[i], 3, i});
    for (int i = 0; i < N-1; i++) {
        if (i < N-2) od.push_back({stt[i+2][0]-stt[i][0], 2, i});
        od.push_back({stt[i+1][0]-stt[i][0], 1, i});
    }
    sort(od.begin(), od.end());

    vector<array<long long, 2>> mn(N, {1000000000LL, 1000000000LL}); //pari, dispari, ci sono solo quelli centrsli i bordi sono a mano
    vector<long long> s(N);
    for (int i = 0; i < N; i++) {
        s[i] = stt[i][1]+stt[i][2];
    }
    vector<array<long long, 2>> infn(N);
    for (int i = 0; i < N; i++) infn[i][0] = i;
    for (int i = 0; i < N; i++) infn[i][1] = i+1;

    vector<long long>  ris(Q);
    long long sum = 0;
    for (int i = 0; i < N; i++) sum += A[i];

    vector<long long> pr(N+1, 0);
    for (int i = 1; i <= N; i++) pr[i] = pr[i-1]+stt[i-1][1];

    for (int k = 0; k < od.size(); k++) {
        array<long long, 3> att = od[k];
        if (att[1] == 1) {
            long long a = fr(att[2]), b = fr(att[2]+1);
            sum -= s[a]; sum -= s[b];
            mn[b] = {min(mn[a][0], mn[b][0]), min(mn[a][1], mn[b][1])};
            infn[b] = {min(infn[a][0], infn[b][0]), max(infn[a][1], infn[b][1])};
            s[b] = pr[infn[b][1]]-pr[infn[b][0]];
            if ((infn[b][1]-infn[b][0])%2) {
                long long dt = 1000000000LL;
                if (infn[b][0]%2) dt = mn[b][0];
                else dt = mn[b][1];
                dt = min(dt, min(stt[infn[b][0]][2], stt[infn[b][1]-1][2]));
                s[b] += dt;
            }
            sum += s[b];
            unite(a, b);
        }
        else if (att[1] == 2) {
            int r = fr(att[2]+1);
            sum -= s[r];
            if (att[2]%2) mn[r][0] = min(mn[r][0], stt[att[2]+1][2]);
            else mn[r][1] = min(mn[r][1], stt[att[2]+1][2]);
            s[r] = pr[infn[r][1]]-pr[infn[r][0]];
            if ((infn[r][1]-infn[r][0])%2) {
                long long dt = 1000000000LL;
                if (infn[r][0]%2) dt = mn[r][0];
                else dt = mn[r][1];
                dt = min(dt, min(stt[infn[r][0]][2], stt[infn[r][1]-1][2]));
                s[r] += dt;
            }
            sum += s[r];
        }
        else ris[att[2]] = sum;
    }
    return ris;
}

Compilation message

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int k = 0; k < od.size(); k++) {
      |                     ~~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 13.0

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

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 21444 KB Output is correct
2 Correct 56 ms 21688 KB Output is correct
3 Correct 58 ms 21048 KB Output is correct
4 Correct 60 ms 21072 KB Output is correct
5 Correct 60 ms 21424 KB Output is correct
6 Correct 66 ms 20920 KB Output is correct

Subtask #4
0.0 / 11.0

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

Subtask #5
0.0 / 20.0

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

Subtask #6
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 21444 KB Output is correct
2 Correct 56 ms 21688 KB Output is correct
3 Correct 58 ms 21048 KB Output is correct
4 Correct 60 ms 21072 KB Output is correct
5 Correct 60 ms 21424 KB Output is correct
6 Correct 66 ms 20920 KB Output is correct
7 Correct 78 ms 25792 KB Output is correct
8 Correct 80 ms 26040 KB Output is correct
9 Correct 88 ms 26100 KB Output is correct
10 Correct 86 ms 26052 KB Output is correct
11 Correct 85 ms 26040 KB Output is correct
12 Correct 87 ms 24404 KB Output is correct
13 Correct 93 ms 26040 KB Output is correct
14 Correct 85 ms 25784 KB Output is correct
15 Correct 89 ms 26040 KB Output is correct

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4176 KB Output is correct
2 Incorrect 3 ms 4432 KB Output isn't correct
3 Halted 0 ms 0 KB -