Submission #1176273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176273		avighna	Two Antennas (JOI19_antennas)	C++20	0 / 100	347 ms	24704 KiB

antennas

#include <bits/stdc++.h>

template <typename T> struct SegmentTree {
  std::vector<T> seg;
  int n;
  std::function<T(T, T)> f;
  T idt;

  SegmentTree(int n, const std::function<T(T, T)> &f, T idt)
      : n(n), f(f), idt(idt) {
    seg.resize(2 * n, idt);
  }

  void set(int idx, T x) {
    for (seg[idx += n] = x; idx > 1; idx /= 2) {
      seg[idx / 2] = f(seg[idx], seg[idx ^ 1]);
    }
  }

  T query(int a, int b) {
    T ans = idt;
    for (a += n, b += n + 1; a < b; a /= 2, b /= 2) {
      if (a & 1) {
        ans = f(ans, seg[a++]);
      }
      if (b & 1) {
        ans = f(ans, seg[--b]);
      }
    }
    return ans;
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n;
  std::cin >> n;
  std::vector<int> h(n), a(n), b(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> h[i] >> a[i] >> b[i];
  }

  auto comm = [&](int i, int j) {
    return (i + a[i] <= j and j <= i + b[i]) or
           (i - b[i] <= j and j <= i - a[i]);
  };

  struct Node {
    int max, min;
  };
  SegmentTree<Node> st(
      n,
      [&](Node a, Node b) {
        return Node({std::max(a.max, b.max), std::min(a.min, b.min)});
      },
      Node({-1, int(1e9) + 1}));
  std::set<std::pair<int, int>> st_l, st_r;
  std::vector<bool> sat_l(n), sat_r(n);
  auto check = [&](int i) {
    if (sat_l[i] and sat_r[i]) {
      st.set(i, Node({h[i], h[i]}));
    } else {
      st.set(i, Node({-1, int(1e9) + 1}));
    }
  };
  for (int i = 0; i < n; ++i) {
    st_l.insert({i - b[i], i});
    st_r.insert({i - a[i], i});
    sat_l[i] = i - b[i] <= 0;
    sat_r[i] = 0 <= i - a[i];
    check(i);
  }

  int q;
  std::cin >> q;
  while (q--) {
    int l, r;
    std::cin >> l >> r;
    --l, --r;
    int ans = -1;
    for (int i = l; i < r; ++i) {
      while (!st_l.empty() and st_l.begin()->first <= i) {
        sat_l[st_l.begin()->second] = true;
        check(st_l.begin()->second);
        st_l.erase(st_l.begin());
      }
      while (!st_r.empty() and i > st_r.begin()->first) {
        sat_r[st_r.begin()->second] = false;
        check(st_r.begin()->second);
        st_r.erase(st_r.begin());
      }
      if (i + a[i] >= n) {
        continue;
      }
      int q_l = i + a[i];
      int q_r = std::min(i + b[i], n - 1);
      Node q = st.query(q_l, q_r);
      if (q.min == -1) {
        continue;
      }
      ans = std::max(ans,
                     std::max(std::abs(h[i] - q.min), std::abs(h[i] - q.max)));
    }
    std::cout << ans << '\n';
  }
}

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