Submission #1105443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105443		LaMatematica14	나일강 (IOI24_nile)	C++17	32 / 100	93 ms	26100 KiB

nile

#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 (stderr)

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
• 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