Submission #557455

#	Time	Username	Problem	Language	Result	Execution time	Memory
557455		erray	Snowball (JOI21_ho_t2)	C++17	100 / 100	86 ms	11384 KiB

Main

// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, Q;
  cin >> N >> Q;
  vector<long long> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  

  vector<int> ord(N - 1);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int x, int y) {
    return A[x + 1] - A[x] < A[y + 1] - A[y];
  });

  long long mn = 0, mx = 0;
  long long cur = 0;
  int p = 0;
  vector<long long> ans(N);
  for (int q = 0; q < Q; ++q) {
    long long W;
    cin >> W;
    cur += W;
    while (p < N - 1 && A[ord[p] + 1] - A[ord[p]] <= max(mx, cur) - min(mn, cur)) {
      int x = ord[p];
      if (cur < mn) {
        ans[x] += mx;
        ans[x + 1] += A[x + 1] - A[x] - mx;
      } else if (cur > mx) {
        ans[x + 1] += -mn;
        ans[x] += A[x + 1] - A[x] + mn; 
      } else {
        assert(false);
      }
      ++p;
    }
    mx = max(mx, cur);
    mn = min(mn, cur);
  }
  debug(ans, mx, mn, p);
  ans[0] -= mn;
  ans[N - 1] += mx;
  for (int i = p; i < N - 1; ++i) {
    ans[ord[i]] += mx;
    ans[ord[i] + 1] -= mn;
  }
  for (int i = 0; i < N; ++i) {
    cout << ans[i] << " \n"[i == N - 1];
  }
}

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