Submission #1150153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150153		cot7302	Two Antennas (JOI19_antennas)	C++20	35 / 100	160 ms	19512 KiB

antennas

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using i64 = long long;
using namespace std;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& X) {
  for (auto& x : X) {
    is >> x;
  }
  return is;
}

template <class T>
constexpr T infty = 0;

template <>
constexpr int infty<int> = 1'000'000'000;

template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;

template <class M>
struct Seg {
  using T = typename M::value_type;
  int N;
  vec<T> tr;
  Seg(int N) : N(N), tr(N * 2, M::unit()) {}

  void set(int i, const T& X) {
    tr[i += N] = X;
    while (i /= 2) {
      tr[i] = M::op(tr[i * 2 + 0], tr[i * 2 + 1]);
    }
  }

  T query(int l, int r) const {
    if (l >= r) {
      return M::unit();
    }
    T ret_l{M::unit()}, ret_r{M::unit()};
    for (l += N, r += N; l < r; l /= 2, r /= 2) {
      if (l & 1) ret_l = M::op(ret_l, tr[l++]);
      if (r & 1) ret_r = M::op(tr[--r], ret_r);
    }
    return M::op(ret_l, ret_r);
  }
};

struct MM {
  using value_type = pair<int, int>;

  static pair<int, int> unit() {
    return {infty<int> + 888, -infty<int> - 888};
  }

  static pair<int, int> op(const pair<int, int>& l, const pair<int, int>& r) {
    return {min(l.first, r.first), max(l.second, r.second)};
  }
};

void subtask2(int N) {
  vec<int> H(N), A(N), B(N);
  for (int i = 0; i < N; i++) {
    cin >> H[i] >> A[i] >> B[i];
  }
  vec<vec<int>> ans(N, vec<int>(N, -infty<int> - 88888));
  Seg<MM> seg(N);
  vec<vec<int>> add(N), del(N + 1);
  auto calc = [&](int l) -> void {
    for (int i = l; i <= N; i++) {
      for (auto j : del[i]) {
        seg.set(j, MM::unit());
      }
      del[i].clear();
      if (i == N) {
        continue;
      }
      for (auto j : add[i]) {
        seg.set(j, {H[j], H[j]});
      }
      add[i].clear();
      if (i != l) {
        ans[l][i] = ans[l][i - 1];
      }
      auto [mn, mx] = seg.query(max(l, i - B[i]), i - A[i] + 1);
      ans[l][i] = max(ans[l][i], max(mx - H[i], H[i] - mn));
      if (i + A[i] < N) {
        add[i + A[i]].emplace_back(i);
      }
      if (i + B[i] + 1 < N) {
        del[i + B[i] + 1].emplace_back(i);
      }
      else {
        del[N].emplace_back(i);
      }
    }
  };
  for (int i = 0; i < N; i++) {
    calc(i);
  }
  int Q; cin >> Q;
  while (Q--) {
    int l, r; cin >> l >> r;
    l -= 1, r -= 1;
    if (ans[l][r] < 0) {
      cout << "-1\n";
    }
    else {
      cout << ans[l][r] << '\n';
    }
  }
  
}

void subtask3(int N) {
  vec<int> H(N), A(N), B(N);
  for (int i = 0; i < N; i++) {
    cin >> H[i] >> A[i] >> B[i];
  }
  int Q; cin >> Q;
  if (Q != 1) {
    return;
  }
  int l, r; cin >> l >> r;
  l -= 1, r -= 1;
  if (l != 0 || r != N - 1) {
    return;
  }
  vec<vec<int>> ans(1, vec<int>(N, -infty<int> - 88888));
  Seg<MM> seg(N);
  vec<vec<int>> add(N), del(N);
  auto calc = [&](int l) -> void {
    for (int i = l; i < N; i++) {
      for (auto j : add[i]) {
        seg.set(j, {H[j], H[j]});
      }
      add[i].clear();
      for (auto j : del[i]) {
        seg.set(j, MM::unit());
      }
      del[i].clear();
      if (i != l) {
        ans[l][i] = ans[l][i - 1];
      }
      auto [mn, mx] = seg.query(max(l, i - B[i]), i - A[i] + 1);
      ans[l][i] = max(ans[l][i], max(mx - H[i], H[i] - mn));
      if (i + A[i] < N) {
        add[i + A[i]].emplace_back(i);
      }
      if (i + B[i] + 1 < N) {
        del[i + B[i] + 1].emplace_back(i);
      }
    }
  };
  for (int i = 0; i < 1; i++) {
    calc(i);
  }
  cout << (ans[0][N - 1] >= 0 ? ans[0][N - 1] : -1) << '\n';
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N; cin >> N;
  if (N <= 2000) {
    subtask2(N);
  }
  else {
    subtask3(N);
  }
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65