Submission #814874

#	Time	Username	Problem	Language	Result	Execution time	Memory
814874		KoD	Radio Towers (IOI22_towers)	C++17	17 / 100	1145 ms	40604 KiB

towers

#include "towers.h"

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

namespace kod {

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using std::begin;
using std::end;

using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;

template <class F> int binary_search(int ok, int ng, const F& f) {
  while (std::abs(ok - ng) > 1) {
    const int md = (ok + ng) / 2;
    (f(md) ? ok : ng) = md;
  }
  return ok;
}

struct sparse_table {
  sparse_table() = default;

  explicit sparse_table(vector<int> a) {
    const int n = (int)a.size();
    table.push_back(std::move(a));
    for (int d = 1;; ++d) {
      const int m = n - (1 << d) + 1;
      if (m <= 0) break;
      table.emplace_back(m, -inf);
      for (int i = 0; i < m; ++i) {
        table[d][i] = std::max(table[d - 1][i], table[d - 1][i + (1 << (d - 1))]);
      }
    }
  }

  int range_max(int l, int r) {
    if (l == r) return -inf;
    const int d = 31 - __builtin_clz(r - l);
    return std::max(table[d][l], table[d][r - (1 << d)]);
  }

 private:
  vector<vector<int>> table;
};

struct Node {
  int l, r, sum;
};
vector<Node> node = {{0, 0, 0}};
int make_node(Node n) {
  node.push_back(std::move(n));
  return (int)node.size() - 1;
}
int make_leaf(int x) { return make_node({0, 0, x}); }
int make_parent(int l, int r) { return make_node({l, r, node[l].sum + node[r].sum}); }
int add(int u, int i, int x, int l, int r) {
  if (r - l == 1) return make_leaf(x);
  const int m = (l + r) / 2;
  if (i < m) return make_parent(add(node[u].l, i, x, l, m), node[u].r);
  return make_parent(node[u].l, add(node[u].r, i, x, m, r));
}
int fold(int u, int i, int j, int l, int r) {
  if (u == 0) return 0;
  if (j <= l || r <= i) return 0;
  if (i <= l && r <= j) return node[u].sum;
  const int m = (l + r) / 2;
  return fold(node[u].l, i, j, l, m) + fold(node[u].r, i, j, m, r);
}

struct segment_tree {
  struct Data {
    int min, max, up, down;
  };

  segment_tree() = default;

  explicit segment_tree(const vector<int>& H) {
    size = (int)H.size();
    data.resize(2 * size, {inf, -inf, -inf, -inf});
    for (int i = 0; i < size; ++i) data[i + size] = {H[i], H[i], -inf, -inf};
    for (int i = size - 1; i > 0; --i) data[i] = merge(data[2 * i], data[2 * i + 1]);
  }

  Data fold(int l, int r) const {
    l += size;
    r += size;
    Data ret_l = {inf, -inf, -inf, -inf};
    Data ret_r = {inf, -inf, -inf, -inf};
    while (l < r) {
      if (l & 1) ret_l = merge(ret_l, data[l++]);
      if (r & 1) ret_r = merge(data[--r], ret_r);
      l >>= 1;
      r >>= 1;
    }
    return merge(ret_l, ret_r);
  }

 private:
  int size;
  vector<Data> data;

  static Data merge(const Data& l, const Data& r) {
    return {std::min(l.min, r.min), std::max(l.max, r.max), std::max({l.up, r.up, r.max - l.min}),
            std::max({l.down, r.down, l.max - r.min})};
  }
};

int N;
vector<int> H, sortedD, nodeID;
sparse_table tableH, tableD;
segment_tree seg;

void init() {
  tableH = sparse_table(H);
  vector<int> D(N, inf), st;
  for (int i = 0; i < N; ++i) {
    while (!st.empty() && H[st.back()] >= H[i]) st.pop_back();
    if (!st.empty()) {
      int j = st.back();
      D[i] = std::min(D[i], tableH.range_max(j, i + 1) - H[i]);
    }
    st.push_back(i);
  }
  st.clear();
  for (int i = N - 1; i >= 0; --i) {
    while (!st.empty() && H[st.back()] > H[i]) st.pop_back();
    if (!st.empty()) {
      int j = st.back();
      D[i] = std::min(D[i], tableH.range_max(i, j + 1) - H[i]);
    }
    st.push_back(i);
  }
  for (int i = 0; i < N; ++i) {
    cerr << D[i] << " \n"[i == N - 1];
  }
  tableD = sparse_table(D);
  vector<int> ord(N);
  std::iota(begin(ord), end(ord), 0);
  std::sort(begin(ord), end(ord), [&](int i, int j) { return D[i] < D[j]; });
  sortedD.resize(N);
  nodeID.resize(N + 1);
  for (int i = N - 1; i >= 0; --i) {
    const int k = ord[i];
    sortedD[i] = D[k];
    nodeID[i] = add(nodeID[i + 1], k, 1, 0, N);
  }
  seg = segment_tree(H);
}

int query(int L, int R, int D) {
  const int id = nodeID[std::lower_bound(begin(sortedD), end(sortedD), D) - begin(sortedD)];
  const int n = fold(id, L, R, 0, N);
  if (n == 0) return 1 + (seg.fold(L, R).up >= D || seg.fold(L, R).down >= D);
  int s = binary_search(R, L, [&](int k) { return tableD.range_max(L, k) >= D; }) - 1;
  int t = binary_search(L, R, [&](int k) { return tableD.range_max(k, R) >= D; });
  int S = binary_search(L, s, [&](int k) { return tableH.range_max(k, s) >= H[s] + D; }) + 1;
  int T = binary_search(R + 1, t, [&](int k) { return tableH.range_max(t, k) >= H[t] + D; }) - 1;
  // cerr << L << ' ' << S << ' ' << s << ' ' << t << ' ' << T << ' ' << R << endl;
  return n + (seg.fold(L, S).up >= D) + (seg.fold(T, R).down >= D);
}

}  // namespace kod

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

int max_towers(int L, int R, int D) { return kod::query(L, R + 1, D); }

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