Submission #680091

#	Time	Username	Problem	Language	Result	Execution time	Memory
680091		tvladm2009	Snowball (JOI21_ho_t2)	C++14	100 / 100	119 ms	16920 KiB

Main

#include <bits/stdc++.h>
#define int ll

using ll = long long;

int const nmax = 200000;

int v[5 + nmax], aux[5 + nmax];
int sp[5 + nmax], mxl[5 + nmax], mxr[5 + nmax];
int sol[5 + nmax];

signed main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);

  int n, q;
  std::cin >> n >> q;
  for(int i = 1;i <= n; i++)
    std::cin >> v[i];
  for(int i = 1;i <= q; i++)
    std::cin >> aux[i];

  for(int i = 1;i <= q; i++) {
    sp[i] = sp[i - 1] + aux[i];
    mxl[i] = std::max(mxl[i - 1], -sp[i]);
    mxr[i] = std::max(mxr[i - 1], sp[i]);
  }
  for(int i = 1;i < n; i++) {
    int result = 0;
    for(int jump = (1 << 18); 0 < jump; jump /= 2)
      if(result + jump <= q && mxl[result + jump] + mxr[result + jump] < v[i + 1] - v[i])
        result += jump;
    result++;
    sol[i] += mxr[result - 1];
    sol[i + 1] += mxl[result - 1];
    if(result <= q) {
      if(aux[result] > 0)
        sol[i] += (v[i + 1] - v[i]) - (mxl[result - 1] + mxr[result - 1]);
      else
        sol[i + 1] += (v[i + 1] - v[i]) - (mxl[result - 1] + mxr[result - 1]);
    }
  }
  sol[1] += mxl[q];
  sol[n] += mxr[q];

  for(int i = 1;i <= n; i++)
    std::cout << sol[i] << "\n";
  return 0;
}

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