| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1102216 | nhphuc | Nile (IOI24_nile) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
void init (vector<int32_t> &a, vector<pair<int, int>> &b){
vector<int32_t> tmp = a;
for (int i = 0; i < b.size(); ++i)
a[i] = tmp[b[i].second];
return;
}
const int N = 100007;
vector<int> par(N), mn(N), sum(N), sz(N), val(N);
int acs (int u){
return (u == par[u] ? u : par[u] = acs(par[u]));
}
vector<int> calculate_costs (
vector<int32_t> w, vector<int32_t> a,
vector<int32_t> b, vector<int32_t> e
){
int n = a.size(), q = e.size();
vector<int> ans(q); vector<pair<int, int>> d(q), x(n), events;
for (int i = 0; i < n; ++i)
x[i] = {w[i], i};
for (int i = 0; i < q; ++i)
d[i] = {e[i], i};
sort(d.begin(), d.end());
sort(x.begin(), x.end());
init(a, x);
init(b, x);
init(w, x);
int res = 0;
for (int i = 0; i < n; ++i){
res += 1ll * a[i];
par[i] = i;
sz[i] = 1;
sum[i] = b[i];
mn[i] = a[i] - b[i];
val[i] = a[i];
}
for (int i = 0; i < n - 1; ++i)
events.push_back({w[i + 1] - w[i], i});
sort(events.begin(), events.end());
int j = 0;
for (auto [x, y] : d){
while (j < events.size() && events[j].first <= x){
int i = events[j].second;
int u = acs(i);
int v = acs(i + 1);
int t = (val[u] + val[v]);
res -= t;
if (sz[u] < sz[v])
swap(u, v);
par[v] = u;
sz[u] += sz[v];
mn[u] = min(mn[u], mn[v]);
sum[u] += sum[v];
val[u] = min((sz[u] % 2ll ? sum[u] + mn[u] : sum[u]), t);
res += val[u];
++j;
}
ans[y] = res;
}
return ans;
}
int32_t main (){
#define task "test"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int n, q; cin >> n >> q;
vector<int32_t> w(n), a(n), b(n), e(q);
for (int32_t &x : w) cin >> x;
for (int32_t &x : a) cin >> x;
for (int32_t &x : b) cin >> x;
for (int32_t &x : e) cin >> x;
vector<int> ans = calculate_costs(w, a, b, e);
for (int x : ans)
cout << x << " ";
}