Submission #1176261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176261		avighna	Two Antennas (JOI19_antennas)	C++20	2 / 100	3094 ms	589824 KiB

antennas

#include <bits/stdc++.h>

struct SegmentTree1D {
  std::vector<int> seg;
  int n;

  SegmentTree1D(int n) : n(n) { seg.resize(2 * n, -1); }

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

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

struct SegmentTree2D {
  std::vector<SegmentTree1D> seg;
  int n;

  SegmentTree2D(int n) : n(n) { seg.resize(2 * n, SegmentTree1D(n)); }

  SegmentTree1D f(const SegmentTree1D &a, const SegmentTree1D &b) {
    SegmentTree1D ans(n);
    for (int i = 0; i < 2 * n; ++i) {
      ans.seg[i] = std::max(a.seg[i], b.seg[i]);
    }
    return ans;
  }

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

  int query(int a, int b, int c, int d) {
    int ans = -1;
    for (a += n, b += n + 1; a < b; a /= 2, b /= 2) {
      if (a & 1) {
        ans = std::max(ans, seg[a++].query(c, d));
      }
      if (b & 1) {
        ans = std::max(ans, seg[--b].query(c, d));
      }
    }
    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]);
  };

  SegmentTree2D st(n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (comm(i, j) and comm(j, i)) {
        st.set(i, j, std::abs(h[i] - h[j]));
      } else {
        st.set(i, j, -1);
      }
    }
  }

  int q;
  std::cin >> q;
  while (q--) {
    int l, r;
    std::cin >> l >> r;
    --l, --r;
    int ans = st.query(l, r, l, r);
    // for (int i = l; i <= r; ++i) {
    //   for (int j = l; j <= r; ++j) {
    //     if (comm(i, j) and comm(j, i)) {
    //       ans = std::max(ans, std::abs(h[i] - h[j]));
    //     }
    //   }
    // }
    std::cout << ans << '\n';
  }
}

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