| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 444502 |
2021-07-14T07:50:42 Z |
palilo |
Snowball (JOI21_ho_t2) |
C++17 |
|
106 ms |
8280 KB |
#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); }
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);
for (auto& x : a) {
cin >> x;
}
vector<pair<int64_t, int>> intervals(n - 1);
for (int i = 0; i < n - 1; ++i) {
intervals[i] = {a[i + 1] - a[i], i};
}
sort(intervals.begin(), intervals.end(), [&](const auto& lhs, const auto& rhs) {
return lhs.first < rhs.first;
});
int ptr = 0;
int64_t lmax = 0, rmax = 0;
vector<int64_t> ans(n);
for (int64_t w, psum = 0; q--;) {
cin >> w;
psum += w;
if (psum < 0) {
for (chmin(lmax, psum); ptr != n - 1 && intervals[ptr].first <= rmax - lmax; ++ptr) {
ans[intervals[ptr].second] += rmax;
ans[intervals[ptr].second + 1] += intervals[ptr].first - rmax;
}
} else {
for (chmax(rmax, psum); ptr != n - 1 && intervals[ptr].first <= rmax - lmax; ++ptr) {
ans[intervals[ptr].second + 1] -= lmax;
ans[intervals[ptr].second] += intervals[ptr].first + lmax;
}
}
}
ans.front() -= lmax;
ans.back() += rmax;
for (; ptr != n - 1; ++ptr) {
ans[intervals[ptr].second] += rmax;
ans[intervals[ptr].second + 1] -= lmax;
}
for (const auto& x : ans) {
cout << x << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
2 ms |
332 KB |
Output is correct |
| 18 |
Correct |
0 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
2 ms |
332 KB |
Output is correct |
| 18 |
Correct |
0 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
31 ms |
288 KB |
Output is correct |
| 21 |
Correct |
33 ms |
204 KB |
Output is correct |
| 22 |
Correct |
29 ms |
316 KB |
Output is correct |
| 23 |
Correct |
26 ms |
368 KB |
Output is correct |
| 24 |
Correct |
31 ms |
1088 KB |
Output is correct |
| 25 |
Correct |
106 ms |
8132 KB |
Output is correct |
| 26 |
Correct |
98 ms |
8116 KB |
Output is correct |
| 27 |
Correct |
94 ms |
7880 KB |
Output is correct |
| 28 |
Correct |
95 ms |
7900 KB |
Output is correct |
| 29 |
Correct |
91 ms |
7692 KB |
Output is correct |
| 30 |
Correct |
80 ms |
7336 KB |
Output is correct |
| 31 |
Correct |
74 ms |
6872 KB |
Output is correct |
| 32 |
Correct |
70 ms |
7008 KB |
Output is correct |
| 33 |
Correct |
10 ms |
1092 KB |
Output is correct |
| 34 |
Correct |
98 ms |
8204 KB |
Output is correct |
| 35 |
Correct |
94 ms |
7892 KB |
Output is correct |
| 36 |
Correct |
98 ms |
8156 KB |
Output is correct |
| 37 |
Correct |
93 ms |
7900 KB |
Output is correct |
| 38 |
Correct |
91 ms |
7900 KB |
Output is correct |
| 39 |
Correct |
101 ms |
7896 KB |
Output is correct |
| 40 |
Correct |
82 ms |
8036 KB |
Output is correct |
| 41 |
Correct |
32 ms |
304 KB |
Output is correct |
| 42 |
Correct |
83 ms |
6872 KB |
Output is correct |
| 43 |
Correct |
89 ms |
8112 KB |
Output is correct |
| 44 |
Correct |
37 ms |
204 KB |
Output is correct |
| 45 |
Correct |
90 ms |
7896 KB |
Output is correct |
| 46 |
Correct |
98 ms |
8280 KB |
Output is correct |
| 47 |
Correct |
97 ms |
8260 KB |
Output is correct |
| 48 |
Correct |
97 ms |
8280 KB |
Output is correct |
