제출 #1166870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166870		kilikuma	Snowball (JOI21_ho_t2)	C++20	33 / 100	1659 ms	9908 KiB

Main

#include <bits/stdc++.h>

#define int long long

using namespace std;

vector<int> w;

vector<tuple<int, int, int>> rightEvents;
vector<tuple<int, int, int>> leftEvents;

int tps(int l, int r) {

  if (l == r)
    return 0;

  if (l < r) {
    if (rightEvents.empty())
      return 2 * (int) (1e17);
    if (get<1>(rightEvents.back()) + l < r)
      return 2 * (int) (1e17);
    int lft = 0, rht = rightEvents.size() - 1, cible = 0;
    while (rht - lft > 1) {
      int mid = (lft + rht) / 2;
      if (get<1>(rightEvents[mid]) + l >= r)
        rht = mid;
      else
        lft = mid;
    }
    if (get<1>(rightEvents[lft]) + l >= r)
      cible = lft;
    else
      cible = rht;
    return get<2>(rightEvents[cible]) + (r - (get<0>(rightEvents[cible]) + l));
  }
  else {
    if (leftEvents.empty())
      return 2 * (int) (1e17);
    if (get<1>(leftEvents.back()) + l > r)
      return 2 * (int) (1e17);
    int lft = 0, rht = leftEvents.size() - 1, cible = 0;
    while (rht - lft > 1) {
      int mid = (lft + rht) / 2;
      if (get<1>(leftEvents[mid]) + l <= r)
        rht = mid;
      else
        lft = mid;
    }
    if (get<1>(leftEvents[lft]) + l <= r)
      cible = lft;
    else
      cible = rht;
    return get<2>(leftEvents[cible]) + (get<0>(leftEvents[cible]) + l - r);
  }

}

int rep(int l, int r) {

  int ans = 0;

  if (l < r) {
    int lft = l, rht = r - 1;
    while (rht - lft > 1) {
      int mid = (lft + rht) / 2;
      if (tps(l, mid + 1) < tps(r, mid))
        lft = mid;
      else
        rht = mid;
    }
    if (tps(l, lft + 1) < tps(r, lft))
      ans = max(ans, lft - l + 1);
    if (tps(l, rht + 1) < tps(r, rht))
      ans = max(ans, rht - l + 1);
  }
  else {
    int lft = r, rht = l - 1;
    while (rht - lft > 1) {
      int mid = (lft + rht) / 2;
      if (tps(r, mid + 1) <= tps(l, mid))
        lft = mid;
      else
        rht = mid;
    }
    if (tps(l, rht) < tps(r, rht + 1))
      ans = max(ans, l - rht);
    if (tps(l, lft) < tps(r, lft + 1))
      ans = max(ans, l - lft);
  }

  return ans;

}

signed main() {

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n, q; cin >> n >> q;

  vector<int> x(n + 2, 0);

  for (int i = 1; i <= n; i ++)
    cin >> x[i];

  x[0] = - 2 * (int) (1e17);
  x[n + 1] = 2 * (int) (1e17);

  w.assign(q + 2, 0);

  for (int i = 1; i <= q; i ++)
    cin >> w[i];

  int posCur = 0, leftExt = 0, rightExt = 0, tpsCur = 0;

  for (int i = 1; i <= q; i ++) {
    if (w[i] > 0) {
      if (w[i] + posCur > rightExt) {
        rightEvents.push_back(make_tuple(rightExt, w[i] + posCur, tpsCur + (rightExt - posCur)));
        rightExt = w[i] + posCur;
      }
    }
    else {
      if (w[i] + posCur < leftExt) {
        leftEvents.push_back(make_tuple(leftExt, w[i] + posCur, tpsCur + (posCur - leftExt)));
        leftExt = w[i] + posCur;
      }
    }
    tpsCur += abs(w[i]);
    posCur += w[i];
  }

  for (int i = 1; i <= n; i ++) {
    cout << rep(x[i], x[i - 1]) + rep(x[i], x[i + 1]) << '\n';
  }

}

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