Submission #548609

#	Time	Username	Problem	Language	Result	Execution time	Memory
548609		MilosMilutinovic	Snowball (JOI21_ho_t2)	C++14	100 / 100	500 ms	13816 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  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> mn(q + 1);
  vector<long long> mx(q + 1);
  long long bal = 0;
  for (int i = 0; i < q; i++) {
    long long w;
    cin >> w;
    bal += w;
    mn[i + 1] = min(mn[i], bal);
    mx[i + 1] = max(mx[i], bal);
  }
  x.push_back(1e18);
  vector<long long> R(n);
  for (int i = 0; i < n; i++) {
    long long low = x[i], high = min(x[i + 1], x[i] + mx[q]) + 1;
    while (low + 1 < high) {
      long long mid = (low + high) >> 1;
      int j = lower_bound(mx.begin(), mx.end(), mid - x[i]) - mx.begin();
      if (x[i + 1] + mn[j] >= mid) {
        low = mid;
      } else {
        high = mid;
      }
    }
    R[i] = low;
  }
  for (int i = 0; i < n; i++) {
    long long L = x[i] + mn[q];
    if (i > 0) {
     L = max(L, R[i - 1]);
    }
    cout << R[i] - L << '\n';
  }
  return 0;
}

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