#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 << " ";
}
Compilation message
nile.cpp: In function 'void init(std::vector<int>&, std::vector<std::pair<long long int, long long int> >&)':
nile.cpp:9:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | for (int i = 0; i < b.size(); ++i)
| ~~^~~~~~~~~~
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:78:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | while (j < events.size() && events[j][0] <= x){
| ~~^~~~~~~~~~~~~~~
nile.cpp: In function 'int32_t main()':
nile.cpp:94:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nile.cpp:95:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc7Ubggu.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccyVEVxu.o:nile.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
