Submission #375746

#	Time	Username	Problem	Language	Result	Execution time	Memory
375746		rama_pang	Snowball (JOI21_ho_t2)	C++14	100 / 100	156 ms	9856 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, Q;
  cin >> N >> Q;
  
  vector<long long> X(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i];
  }

  vector<long long> W(Q);
  for (int i = 0; i < Q; i++) {
    cin >> W[i];
  }

  long long current_x = 0;
  vector<long long> L(Q + 1), R(Q + 1);
  for (int i = 1; i <= Q; i++) {
    current_x += W[i - 1];
    L[i] = min(L[i - 1], current_x);
    R[i] = max(R[i - 1], current_x);
  }

  vector<long long> ans(N);
  for (int i = 0; i < N; i++) {
    long long ansL, ansR;
    if (i == 0) {
      ansL = X[i] + L[Q];
    } else {
      int lo = 0, hi = Q;
      while (lo < hi) {
        int md = (lo + hi + 1) / 2;
        if (X[i - 1] + R[md] <= X[i] + L[md]) {
          lo = md;
        } else {
          hi = md - 1;
        }
      }
      assert(X[i - 1] + R[lo] <= X[i] + L[lo]);
      if (lo < Q && W[lo] < 0) {
        ansL = X[i - 1] + R[lo];
      } else {
        ansL = X[i] + L[lo];
      }
    }
    if (i + 1 == N) {
      ansR = X[i] + R[Q];
    } else {
      int lo = 0, hi = Q;
      while (lo < hi) {
        int md = (lo + hi + 1) / 2;
        if (X[i] + R[md] <= X[i + 1] + L[md]) {
          lo = md;
        } else {
          hi = md - 1;
        }
      }
      assert(X[i] + R[lo] <= X[i + 1] + L[lo]);
      if (lo < Q && W[lo] > 0) {
        ansR = X[i + 1] + L[lo];
      } else {
        ansR = X[i] + R[lo];
      }
    }
    ans[i] = ansR - ansL;
  }

  for (int i = 0; i < N; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

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