#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 ==)
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
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from nile.cpp:1:
nile.cpp: In member function 'int DSU::unite(int, int, int)':
nile.cpp:57:13: error: expected primary-expression before ')' token
57 | assert(a ==)
| ^~~~~~
nile.cpp:54:17: warning: unused variable 'p' [-Wunused-variable]
54 | int p = (a + 1) % 2;
| ^
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) {
| ~~^~~~~~~~~~~~~~
