Submission #1111239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111239		popabogdannnn	Nile (IOI24_nile)	C++17	100 / 100	94 ms	15568 KiB

nile

#include <bits/stdc++.h>

using namespace std;

struct Artifact {
    int W, C;
};

struct Edge {
    int a, b, c;
};

struct DSU {
    struct Info {
        int cost;
        int le, ri;
        int min_alone[2];
        int min_over[2];
        Info() = default;
        Info(int pos, int val) {
            le = ri = pos;
            min_alone[0] = min_alone[1] = INT_MAX;
            min_over[0] = min_over[1] = INT_MAX;
            min_alone[pos % 2] = val;
            cost = val;
        }
    };

    vector<int>T;
    vector<Info> info;

    long long init(vector<Artifact> artifacts) {
        int N = artifacts.size();
        long long ret = 0;
        T.resize(N);
        info.resize(N);
        iota(T.begin(), T.end(), 0);
        for(int i = 0; i < N; i++) {
            info[i] = Info(i, artifacts[i].C);
            ret += artifacts[i].C;
        }
        return ret;
    };

    int find(int a) {
        if(a == T[a]) {
            return a;
        }
        return T[a] = find(T[a]);
    }

    int unite(int a, int b, int c) {
        if(b == a + 2) {
            int p = (a + 1) % 2;
            a = find(a);
            b = find(b);
            assert(a == b);
            info[a].min_over[p] = min(info[a].min_over[p], c);
            int ret = -info[a].cost;
            if((info[a].ri - info[a].le + 1) % 2 == 1) {
                info[a].cost = min(info[a].cost, info[a].min_over[1 - info[a].le % 2]);
            }
            return ret + info[a].cost;
        }
        a = find(a);
        b = find(b);

        int ret = -info[a].cost - info[b].cost;
        info[b].le = min(info[b].le, info[a].le);
        info[b].ri = max(info[b].ri, info[a].ri);
        info[b].min_alone[0] = min(info[b].min_alone[0], info[a].min_alone[0]);
        info[b].min_alone[1] = min(info[b].min_alone[1], info[a].min_alone[1]);
        info[b].min_over[0] = min(info[b].min_over[0], info[a].min_over[0]);
        info[b].min_over[1] = min(info[b].min_over[1], info[a].min_over[1]);
        T[a] = b;
        
        if((info[b].ri - info[b].le + 1) % 2 == 1) {
            info[b].cost = min(info[b].min_alone[info[b].le % 2], info[b].min_over[1 - info[b].le % 2]);
        }
        else {
            info[b].cost = 0;
        }
        return ret + info[b].cost;
    }

};

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(), Q = E.size();    
    vector<Artifact> artifacts(N);
    vector<pair <int, int>> queries(Q);
    vector<long long> ret(Q);
    vector<Edge> edges;

    long long ans = 0;
    for(int i = 0; i < N; i++) {
        artifacts[i] = {W[i], A[i] - B[i]};
        ans += B[i];
    }
    for(int i = 0; i < Q; i++) {
        queries[i] = {E[i], i};
    }
    sort(queries.begin(), queries.end());

    sort(artifacts.begin(), artifacts.end(), [](Artifact a, Artifact b) {
        return a.W < b.W;
    });

    for(int i = 0; i + 1 < N; i++) {
        edges.push_back({i, i + 1, artifacts[i + 1].W - artifacts[i].W});
        if(i + 2 < N) {
            edges.push_back({i, i + 2, artifacts[i + 2].W - artifacts[i].W});
        }
    }
    
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
        return a.c < b.c || (a.c == b.c && (a.b - a.a) < (b.b - b.a));
    });
    DSU dsu;
    ans += dsu.init(artifacts);
    
    int j = 0;
    for(int i = 0; i < Q; i++) {
        while(j < edges.size() && edges[j].c <= queries[i].first) {
            ans += dsu.unite(edges[j].a, edges[j].b, artifacts[edges[j].a + 1].C);
            j++;
        }
        ret[queries[i].second] = ans;
    }
    return ret;
}

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:124:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         while(j < edges.size() && edges[j].c <= queries[i].first) {
      |               ~~^~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18