# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
599057 | jmyszka2007 | Snowball (JOI21_ho_t2) | C++17 | 133 ms | 12916 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;
constexpr int MAXN = 2 * 1e5;
typedef long long ll;
ll s[MAXN + 10];
ll mx[MAXN + 10];
ll mn[MAXN + 10];
ll tab[MAXN + 10];
ll w[MAXN + 10];
ll res[MAXN + 10];
int bs(int l, int r, ll x) {
while(l < r) {
int mid = (l + r + 1) / 2;
if((mx[mid] - mn[mid]) <= x) {
l = mid;
}
else {
r = mid - 1;
}
}
return l;
}
int main() {
int n, t;
scanf("%d%d", &n, &t);
for(int i = 1; i <= n; i++) {
scanf("%lld", &tab[i]);
}
for(int i = 1; i <= t; i++) {
scanf("%lld", &w[i]);
s[i] = s[i - 1] + w[i];
mx[i] = max(mx[i - 1], s[i]);
mn[i] = min(mn[i - 1], s[i]);
}
for(int i = 1; i < n; i++) {
ll d = tab[i + 1] - tab[i];
int m = bs(0, t, d);
res[i] += mx[m];
res[i + 1] += mn[m] * -1;
if(m == t) {
continue;
}
if(w[m + 1] >= 0) {
res[i] += (d - mx[m] + mn[m]);
}
else {
res[i + 1] += (d - mx[m] + mn[m]);
}
}
res[1] += mn[t] * -1;
res[n] += mx[t];
for(int i = 1; i <= n; i++) {
printf("%lld ", res[i]);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |