Submission #1176262

#TimeUsernameProblemLanguageResultExecution timeMemory
1176262avighnaTwo Antennas (JOI19_antennas)C++20
13 / 100
316 ms589824 KiB
#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, const SegmentTree1D &x) {
    for (seg[i += n] = x; 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) {
    SegmentTree1D st1d(n);
    for (int j = 0; j < n; ++j) {
      if (comm(i, j) and comm(j, i)) {
        st1d.set(j, std::abs(h[i] - h[j]));
      }
    }
    st.set(i, st1d);
  }

  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';
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...