Submission #1176514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176514		avighna	Two Antennas (JOI19_antennas)	C++20	22 / 100	581 ms	34960 KiB

antennas

#include <bits/stdc++.h>

template <typename T> class SegmentTree {
public:
  std::vector<T> seg;
  int n;

  SegmentTree(int n) : n(n) { seg.resize(2 * n, int(1e9) + 1); }

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

  T query(int l, int r) {
    T ans = int(1e9) + 1;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) {
        ans = std::min(ans, seg[l++]);
      }
      if (r & 1) {
        ans = std::min(ans, seg[--r]);
      }
    }
    return ans;
  }
};

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

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

  void lazy_update(int v, int tl, int tr) {
    if (lazy[v] != -1) {
      seg[v] = std::max(seg[v], lazy[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;
    }
  }

  // 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,
              SegmentTree<T> &tree) {
    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 - tree.query(tl, tr));
      lazy_update(v, tl, tr);
      return;
    }
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, r, x, tree);
    update(2 * v + 1, tm + 1, tr, l, r, x, tree);
    seg[v] = std::max(seg[2 * v], seg[2 * v + 1]);
  };
  void update(int l, int r, int x, SegmentTree<T> &tree) {
    update(1, 0, n - 1, l, r, x, tree);
  }

  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) {
  // your code here
  std::sort(queries.begin(), queries.end(),
            [](Query a, Query b) { return a.r > b.r; });
  SegmentTree<int> tree(n);
  LazySegmentTree<int> st(n);
  std::vector<bool> sat_b(n), sat_a(n), sat_c(n);
  auto check = [&](int i) {
    if (sat_a[i] and sat_b[i] and sat_c[i]) {
      tree.set(i, h[i]);
    } else {
      tree.set(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());
    }
    // r-b[r], r-a[r]
    st.update(r - b[r], r - a[r], h[r], tree);
    while (!queries.empty() and queries.back().r == r) {
      auto [l, r, i] = queries.back();
      ans[i] = st.query(l, r);
      queries.pop_back();
    }
    sat_c[r] = true;
  }
  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: 0 / 2
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65