Submission #910116

#TimeUsernameProblemLanguageResultExecution timeMemory
910116vjudge1Snowball (JOI21_ho_t2)C++17
100 / 100
387 ms13896 KiB
#include <bits/stdc++.h>
using namespace std;

#define SIZE 200005
#define infl LLONG_MAX / 3

using ll = long long;

ll n, q, x[SIZE], ans[SIZE];
pair<ll, ll> t[SIZE];
int main(void) {
  cin >> n >> q;
  x[0] = -infl, x[n + 1] = infl;
  for (int i = 1; i <= n; i++) cin >> x[i];
  for (int i = 0; i <= n; i++) {
    t[i] = make_pair(x[i + 1] - x[i], i);
  }
  sort(t, t + n + 1);
  ll l = 0, r = 0, v = 0;
  int p = 0;
  while (q--) {
    ll w;
    cin >> w;
    if (w >= 0) {
      v += w;
      r = max(r, v);
      while (p <= n && t[p].first < l + r) {
        ans[t[p].second + 1] += l;
        ans[t[p].second] += t[p].first - l;
        p++;
      }
    } else {
      v += w;
      l = max(l, -v);
      while (p <= n && t[p].first < l + r) {
        ans[t[p].second] += r;
        ans[t[p].second + 1] += t[p].first - r;
        p++;
      }
    }
  }
  while (p <= n) {
    ans[t[p].second] += r;
    ans[t[p].second + 1] += l;
    p++;
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << endl;
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...