Submission #371039

#	Time	Username	Problem	Language	Result	Execution time	Memory
371039		valerikk	Snowball (JOI21_ho_t2)	C++17	100 / 100	1333 ms	10020 KiB

Main

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector <ll> x(n);
  for (int i = 0; i < n; i++) cin >> x[i];
  vector <ll> w(q);
  for (int i = 0; i < q; i++) cin >> w[i];
  vector <ll> pref_mn(q + 1), pref_mx(q + 1);
  pref_mn[0] = pref_mx[0] = 0;
  ll sum = 0;
  for (int i = 0; i < q; i++) {
    sum += w[i];
    pref_mn[i + 1] = min(pref_mn[i], sum);
    pref_mx[i + 1] = max(pref_mx[i], sum);
  }
  auto get_mn = [&](ll val) {
    int l = -1, r = q + 1;
    while (r - l > 1) {
      int m = (l + r) / 2;
      if (pref_mn[m] <= val) r = m; else l = m;
    }
    return r;
  };
  auto get_mx = [&](ll val) {
    int l = -1, r = q + 1;
    while (r - l > 1) {
      int m = (l + r) / 2;
      if (pref_mx[m] >= val) r = m; else l = m;
    }
    return r;
  };
  ll mn = pref_mn[q], mx = pref_mx[q];
  vector <ll> ans(n, 0);
  ans[0] += -mn;
  ans[n - 1] += mx;
  for (int i = 0; i + 1 < n; i++) {
    if (x[i] + mx < x[i + 1] + mn) {
      ans[i] += mx;
      ans[i + 1] += -mn;
      continue;
    }
    ll l = x[i], r = x[i + 1] + 1;
    while (r - l > 1) {
      ll m = (l + r) / 2;
      if (get_mx(m - x[i]) < get_mn(m - 1 - x[i + 1])) l = m; else r = m;
    }
    ans[i] += l - x[i];
    ans[i + 1] += x[i + 1] - l;
  }
  for (int i = 0; i < n; i++) cout << ans[i] << '\n';
  cout << endl;
  return 0;
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67