Submission #1176580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176580		avighna	Two Antennas (JOI19_antennas)	C++20	100 / 100	832 ms	44564 KiB

antennas

#include <bits/stdc++.h>

template <typename T> class LazySegmentTree {
public:
  std::vector<T> seg;
  std::vector<T> lazy;
  std::vector<T> seg_min;
  int n;

  LazySegmentTree(int n) : n(n) {
    seg.resize(4 * n, -1);
    lazy.resize(8 * n, -1);
    seg_min.resize(4 * n, int(1e9) + 1);
  }

  void lazy_update(int v, int tl, int tr) {
    if (lazy[v] != -1) {
      seg[v] = std::max(seg[v], lazy[v] - seg_min[v]);
      lazy[2 * v] = std::max(lazy[2 * v], lazy[v]);
      lazy[2 * v + 1] = std::max(lazy[2 * v + 1], lazy[v]);
      lazy[v] = -1;
    }
  }

  void set_min(int v, int tl, int tr, int idx, int x) {
    lazy_update(v, tl, tr);
    if (tr < idx or idx < tl or tl > tr) {
      return;
    }
    if (tl == tr) {
      seg_min[v] = x;
      return;
    }
    int tm = (tl + tr) / 2;
    set_min(2 * v, tl, tm, idx, x);
    set_min(2 * v + 1, tm + 1, tr, idx, x);
    seg_min[v] = std::min(seg_min[2 * v], seg_min[2 * v + 1]);
  }
  void set_min(int idx, int x) { set_min(1, 0, n - 1, idx, x); }

  // v = max(v, x - seg_min[v]) for v in [l, r]
  void update(int v, int tl, int tr, int l, int r, int x) {
    lazy_update(v, tl, tr);
    if (tr < l or r < tl or tl > tr or l > r) {
      return;
    }
    if (l <= tl and tr <= r) {
      lazy[v] = std::max(lazy[v], x);
      lazy_update(v, tl, tr);
      return;
    }
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, r, x);
    update(2 * v + 1, tm + 1, tr, l, r, x);
    seg[v] = std::max(seg[2 * v], seg[2 * v + 1]);
  };
  void update(int l, int r, int x) { update(1, 0, n - 1, l, r, x); }

  T query(int v, int tl, int tr, int l, int r) {
    lazy_update(v, tl, tr);
    if (tr < l or r < tl or tl > tr or l > r) {
      return -1;
    }
    if (l <= tl and tr <= r) {
      return seg[v];
    }
    int tm = (tl + tr) / 2;
    return std::max(query(2 * v, tl, tm, l, r),
                    query(2 * v + 1, tm + 1, tr, l, r));
  };
  T query(int l, int r) { return query(1, 0, n - 1, l, r); }
};

struct Query {
  int l, r;
  int i;
};

std::vector<int> solve(int n, std::vector<int> h, std::vector<int> a,
                       std::vector<int> b, int q, std::vector<Query> queries) {
  std::sort(queries.begin(), queries.end(),
            [](Query a, Query b) { return a.r > b.r; });
  LazySegmentTree<int> st(n);
  std::vector<bool> sat_b(n), sat_a(n);
  auto check = [&](int i) {
    if (sat_a[i] and sat_b[i]) {
      st.set_min(i, h[i]);
    } else {
      st.set_min(i, int(1e9) + 1);
    }
  };
  std::set<std::pair<int, int>> st_a, st_b;
  for (int i = 0; i < n; ++i) {
    if (i + a[i] <= 0) {
      sat_a[i] = true;
    }
    if (0 <= i + b[i]) {
      sat_b[i] = true;
    }
    st_a.insert({i + a[i], i});
    st_b.insert({i + b[i], i});
    check(i);
  }

  std::vector<int> ans(q);
  for (int r = 0; r < n; ++r) {
    while (!st_a.empty() and st_a.begin()->first <= r) {
      sat_a[st_a.begin()->second] = true;
      check(st_a.begin()->second);
      st_a.erase(st_a.begin());
    }
    while (!st_b.empty() and r > st_b.begin()->first) {
      sat_b[st_b.begin()->second] = false;
      check(st_b.begin()->second);
      st_b.erase(st_b.begin());
    }
    st.update(r - b[r], r - a[r], h[r]);
    while (!queries.empty() and queries.back().r == r) {
      auto [l, r, i] = queries.back();
      ans[i] = st.query(l, r);
      queries.pop_back();
    }
  }
  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];
  }

  int q;
  std::cin >> q;
  std::vector<Query> queries(q);
  for (int i = 0, l, r; i < q; ++i) {
    std::cin >> l >> r;
    --l, --r;
    queries[i] = {l, r, i};
  }
  std::vector<int> ans1 = solve(n, h, a, b, q, queries);
  std::reverse(h.begin(), h.end());
  std::reverse(a.begin(), a.end());
  std::reverse(b.begin(), b.end());
  for (auto &[l, r, i] : queries) {
    std::swap(l, r);
    l = n - l - 1, r = n - r - 1;
  }
  std::vector<int> ans2 = solve(n, h, a, b, q, queries);
  for (int i = 0; i < q; ++i) {
    std::cout << std::max(ans1[i], ans2[i]) << '\n';
  }
}

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