| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1102257 | 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;
}
bool cmp (array<int, 3> a, array<int, 3> b){
for (int i = 0; i < 3; ++i)
if (a[i] < b[i])
return true;
else
if (a[i] > b[i])
return false;
return true;
}
const int inf = 1e12;
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();
set<int> st;
vector<int> ans(q), c(n), sz(n);
vector<pair<int, int>> d(q), x(n);
vector<array<int, 3>> events, mn(n, {inf, inf, inf});
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 = accumulate(b.begin(), b.end(), 0ll), add = 0;
for (int i = 0; i < n; ++i){
st.insert(i);
c[i] = a[i] - b[i];
sz[i] = 1;
mn[i][i & 1] = c[i];
add += c[i];
if (i + 1 < n)
events.push_back({w[i + 1] - w[i], i, 0});
if (i + 2 < n)
events.push_back({w[i + 2] - w[i], i, 1});
}
sort(events.begin(), events.end());
auto fi = [&] (int i){
return min(mn[i][i & 1], mn[i][2]) * (sz[i] & 1);
};
auto u1 = [&] (int i){
int j = *prev(st.upper_bound(i));
int k = i + 1;
add -= (fi(j) + fi(k));
st.erase(k);
sz[j] += sz[k];
for (int l = 0; l < 3; ++l)
mn[j][l] = min(mn[j][l], mn[k][l]);
add += fi(j);
};
auto u2 = [&] (int i){
int j = *prev(st.upper_bound(i));
add -= fi(j);
mn[j][2] = min(mn[j][2], c[i + 1]);
add += fi(j);
};
int j = 0;
for (auto [x, y] : d){
while (j < events.size() && events[j][0] <= x){
int i = events[j][1];
if (events[j][2])
u2(i);
else
u1(i);
++j;
}
ans[y] = res + add;
}
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 << " ";
}