#include <bits/stdc++.h>
using namespace std;
template <class T>
bool chmin(T& _old, T _new) { return _old > _new && (_old = _new, true); }
template <class T>
bool chmax(T& _old, T _new) { return _old < _new && (_old = _new, true); }
#ifdef palilo
template <typename C, typename T = decay_t<decltype(*begin(declval<C>()))>,
typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator<<(ostream& os, const C& container) {
stringstream ss;
ss << '[';
bool first = true;
for (const auto& x : container) {
if (!first) ss << ", ";
first = false;
ss << x;
}
ss << ']';
return os << ss.str();
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
stringstream ss;
ss << '(' << p.first << ", " << p.second << ')';
return os << ss.str();
}
template <typename T>
void debug_msg(string name, T arg) {
cerr << name << " = " << arg << endl;
}
template <typename T1, typename... T2>
void debug_msg(string names, T1 arg, T2... args) {
cerr << names.substr(0, names.find(',')) << " = " << arg << " | ";
debug_msg(names.substr(names.find(',') + 2), args...);
}
#define debug(...) cerr << '(' << __LINE__ << ')' << ' ', debug_msg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...)
#endif
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef palilo
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#endif
int n, q;
cin >> n >> q;
vector<int64_t> a(n), w(q);
for (auto& x : a) {
cin >> x;
}
for (auto& x : w) {
cin >> x;
}
partial_sum(w.begin(), w.end(), w.begin());
w.erase(remove(w.begin(), w.end(), 0), w.end());
if (w.empty()) {
for (int i = 0; i < n; ++i) {
cout << "0\n";
}
return 0;
}
vector<int64_t> d;
for (int i = 0, j; i != int(w.size()); i = j) {
const bool lhs = w[i] < 0;
int64_t farthest = w[i];
for (j = i + 1; j != int(w.size()); ++j) {
if (lhs) {
if (w[j] > 0) {
break;
}
chmin(farthest, w[j]);
} else {
if (w[j] < 0) {
break;
}
chmax(farthest, w[j]);
}
}
if (d.size() < 3 || abs(farthest) > abs(d.end()[-2])) {
d.emplace_back(farthest);
}
}
assert(d.size());
if (d.size() == 1) {
const bool lhs = d.front() < 0;
const auto snow = abs(d.front());
cout << (lhs ? snow : 0) << ' ';
for (int i = 1; i < n - 1; ++i) {
cout << min(snow, a[i + 1 - lhs] - a[i - lhs]) << ' ';
}
cout << (lhs ? 0 : snow);
return 0;
}
auto binary = [&](int64_t val) {
int lo = 0, hi = d.size() - 2;
while (lo != hi) {
const int mid = (lo + hi) >> 1;
abs(d[mid]) + abs(d[mid + 1]) < val ? lo = mid + 1 : hi = mid;
}
return lo;
};
debug(d);
vector<int64_t> ans(n);
ans.front() -= min(d.end()[-2], d.end()[-1]);
ans.back() += max(d.end()[-2], d.end()[-1]);
for (int i = 0; i < n - 1; ++i) {
auto gap = a[i + 1] - a[i];
const auto it = binary(gap);
if (d[it] < 0) {
auto snow = min(gap, -d[it]);
ans[i + 1] += snow, gap -= snow;
ans[i] += min(gap, d[it + 1]);
} else {
auto snow = min(gap, d[it]);
ans[i] += snow, gap -= snow;
ans[i + 1] += min(gap, -d[it + 1]);
}
}
for (const auto& x : ans) {
cout << x << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
448 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
448 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
