제출 #910116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
910116		vjudge1	Snowball (JOI21_ho_t2)	C++17	100 / 100	387 ms	13896 KiB

Main

#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;
  }
}

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