Submission #798509

#	Time	Username	Problem	Language	Result	Execution time	Memory
798509		jakobrs	Radio Towers (IOI22_towers)	C++17	56 / 100	944 ms	24000 KiB

towers

#include <optional>
#include <unordered_set>
#include <vector>
#include <algorithm>

#ifndef EVAL
#include <format>
#include <iostream>

template <typename... Args>
void print(std::format_string<Args...> fmt, Args &&...args) {
  std::cerr << std::format(fmt, std::forward<Args>(args)...);
}

template <typename... Args>
void println(std::format_string<Args...> fmt, Args &&...args) {
  std::cerr << std::format(fmt, std::forward<Args>(args)...) << '\n';
}
#else
template <typename... T> void print(T &&...args) {}
template <typename... T> void println(T &&...args) {}
#endif

int n;
std::vector<int> h;

void init(int N, std::vector<int> H) {
  n = N;
  h = H;
}

template <typename Node> struct SegmentTree {
  std::vector<Node> nodes;
  int offset;

  explicit SegmentTree(int sz) : nodes(2 * sz), offset(sz) {}

  void update(int idx, const Node &node) {
    idx += offset;
    nodes[idx] = node;

    while (idx /= 2) {
      nodes[idx] = nodes[2 * idx] * nodes[2 * idx + 1];
    }
  }

  Node query(int l, int r) const {
    Node left, right;

    l += offset;
    r += offset;

    while (l < r) {
      if (l & 1)
        left = left * nodes[l++];
      if (r & 1)
        right = nodes[--r] * right;

      l >>= 1;
      r >>= 1;
    }

    return left * right;
  }
};

int d;

struct LeftNode {
  int a, b, min, max;

  LeftNode() : a(-1), b(-1), min(2'000'000'000), max(-2'000'000'000) {}
  LeftNode(int a) : a(-1), b(-1), min(a), max(a) {}
  LeftNode(int a, int b, int min, int max) : a(a), b(b), min(min), max(max) {}

  LeftNode operator*(const LeftNode &rhs) const {
    std::pair<int, int> c1 = {b, a};
    std::pair<int, int> c2 = {rhs.b, rhs.a};
    std::pair<int, int> c3 = {-1, -1};
    if (rhs.max >= 0 && rhs.max - min >= d) {
      c3 = {rhs.max, min};
    }

    std::pair<int, int> best = std::max(std::max(c1, c2), c3);

    return {best.second, best.first, std::min(min, rhs.min),
            std::max(max, rhs.max)};
  }
};
struct RightNode {
  int a, b, min, max;

  RightNode() : a(-1), b(-1), min(2'000'000'000), max(-2'000'000'000) {}
  RightNode(int a) : a(-1), b(-1), min(a), max(a) {}
  RightNode(int a, int b, int min, int max) : a(a), b(b), min(min), max(max) {}

  RightNode operator*(const RightNode &rhs) const {
    std::pair<int, int> c1 = {b, a};
    std::pair<int, int> c2 = {rhs.b, rhs.a};
    std::pair<int, int> c3 = {-1, -1};
    if (max >= 0 && max - rhs.min >= d) {
      c3 = {max, rhs.min};
    }

    std::pair<int, int> best = std::max(std::max(c1, c2), c3);

    return {best.second, best.first, std::min(min, rhs.min),
            std::max(max, rhs.max)};
  }
};

struct PrecomputedData {
  std::unordered_set<int> included_s;
  std::vector<int> prefix_sums, prev, next;

  SegmentTree<LeftNode> left_st;
  SegmentTree<RightNode> right_st;
};

std::optional<PrecomputedData> precomputed;

int max_towers(int L, int R, int D) {
  if (L == R)
    return 1;
  R += 1;

  if (!precomputed) {
    d = D;
    std::vector<int> included{h[0]};
    int intermediary = h[0];
    for (int i = 1; i < n; i++) {
      if (h[i] > intermediary) {
        // println("Found new intermediary: {}", h[i]);
        intermediary = h[i];
      } else if (intermediary - included.back() < D) {
        if (h[i] < included.back()) {
          // println("Found better tower: {} instead of {}", h[i],
          // included.back());
          included.pop_back();
          included.push_back(h[i]);
          intermediary = h[i];
        } else {
          // println("Found new tower, but it's worse: {} instead of {}",
          // h[i], included.back());
        }
      } else if (intermediary - h[i] >= D) {
        // println("Found new tower: {} (previous was {}, greatest: {})",
        // h[i], included.back(), greatest);
        included.push_back(h[i]);
        intermediary = h[i];
      }
    }

    std::unordered_set<int> included_s(included.begin(), included.end());

    std::vector<int> prev, next;
    int prev_val = -1;
    for (int i = 0; i < n; i++) {
      if (included_s.count(h[i])) {
        prev_val = i;
      }
      prev.push_back(prev_val);
    }
    int next_val = -1;
    for (int i = n - 1; i >= 0; i--) {
      if (included_s.count(h[i])) {
        next_val = i;
      }
      next.push_back(next_val);
    }
    std::reverse(next.begin(), next.end());
    std::vector<int> prefix_sums{1};
    prefix_sums.reserve(n + 1);
    for (int i = 0; i < n; i++) {
      prefix_sums.push_back(prefix_sums.back() + included_s.count(h[i]));
    }

    int o = 1;
    while (o < n)
      o *= 2;

    SegmentTree<LeftNode> left_st(o);
    SegmentTree<RightNode> right_st(o);

    for (int i = 0; i < n; i++) {
      left_st.update(i, LeftNode(h[i]));
      right_st.update(i, RightNode(h[i]));
    }

    precomputed = std::make_optional(PrecomputedData{
        included_s, prefix_sums, prev, next, left_st, right_st});
  }

  int total = precomputed->prefix_sums[R] - precomputed->prefix_sums[L];

  int next = precomputed->next[L];
  auto q0 = precomputed->left_st.query(L, next);
  if (q0.b - h[next] >= D) {
    total += 1;
  }

  int prev = precomputed->prev[R - 1];
  auto q1 = precomputed->right_st.query(prev + 1, R);
  if (q1.b - h[prev] >= D) {
    total += 1;
  }

  return std::max(total, 1);
}

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 0 / 17
• Subtask 6: 19 / 19
• Subtask 7: 0 / 23