Submission #1150188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150188		cot7302	Two Antennas (JOI19_antennas)	C++20	0 / 100	158 ms	21828 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 AM>
struct Seg {
  using A = typename AM::Act;
  using M = typename AM::Monoid;
  using G = typename A::value_type;
  using T = typename M::value_type;
  int N, log;
  vec<G> tg;
  vec<T> tr;

  Seg(int N) : N(N), log(__lg(N) + 1), tg(N, A::unit()), tr(N * 2, M::unit()) {}

  void __apply(int i, const G& t) {
    tr[i] = AM::act(tr[i], t);
    if (i < N) {
      tg[i] = A::op(tg[i], t);
    }
  }

  void push(int id) {
    id += N;
    for (int h = log; h > 0; h--) {
      int i = id >> h;
      if (tg[i] != A::unit()) {
        __apply(i * 2 + 0, tg[i]);
        __apply(i * 2 + 1, tg[i]);
        tg[i] = A::unit();
      }
    }
  }

  void pull(int i) {
    for (i += N; i /= 2; ) {
      tr[i] = M::op(tr[i * 2 + 0], tr[i * 2 + 1]);
      if (tg[i] != A::unit()) {
        tr[i] = AM::act(tr[i], tg[i]);
      }
    }
  }

  void set(int i, const T& X) {
    push(i);
    tr[i + N] = X;
    pull(i);
  }

  void apply(int l, int r, const G& t) {
    if (l >= r) {
      return;
    }
    int il = l, ir = r;
    push(il), push(ir - 1);
    for (l += N, r += N; l < r; l /= 2, r /= 2) {
      if (l & 1) __apply(l++, t);
      if (r & 1) __apply(--r, t);
    }
    pull(il), pull(ir - 1);
  }

  T query(int l, int r) {
    if (l >= r) {
      return M::unit();
    }
    push(l), push(r - 1);
    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 AM {
  struct Act {
    using value_type = int;

    static int unit() {
      return infty<int> + 8888;
    }

    static int op(int l, int r) {
      return max(l, r);
    }
  };

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

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

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

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

void calc(int N, const vec<int>& H, const vec<int>& A, const vec<int>& B, const vec<vec<int>>& add, const vec<vec<int>>& del, const vec<vec<pair<int, int>>>& qq, vec<int>& ans) {
  Seg<AM> seg(N);
  for (int i = 0; i < N; i++) {
    for (auto j : add[i]) {
      seg.set(j, {-infty<int>, H[j]});
    }
    for (auto j : del[i]) {
      seg.set(j, {-infty<int>, infty<int> + 888888});
    }
    seg.apply(max(0, i - B[i]), max(0, i - A[i] + 1), H[i]);
    for (auto [l, id] : qq[i]) {
      ans[id] = max(ans[id], seg.query(l, i + 1).first);
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N; cin >> N;
  vec<int> H(N), A(N), B(N);
  vec<vec<int>> add(N), del(N);
  for (int i = 0; i < N; i++) {
    cin >> H[i] >> A[i] >> B[i];
    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);
    }
  }
  int Q; cin >> Q;
  vec<vec<pair<int, int>>> qq(N);
  vec<int> ans(Q, -infty<int>);
  for (int i = 0; i < Q; i++) {
    int l, r; cin >> l >> r;
    l -= 1, r -= 1;
    qq[r].emplace_back(l, i);
  }
  calc(N, H, A, B, add, del, qq, ans);
  for (auto& h : H) {
    h = -h;
  }
  calc(N, H, A, B, add, del, qq, ans);
  for (int i = 0; i < Q; i++) {
    if (ans[i] < 0) {
      cout << "-1\n";
    }
    else {
      cout << ans[i] << '\n';
    }
  }
}

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