Submission #625448

#	Time	Username	Problem	Language	Result	Execution time	Memory
625448		model_code	Radio Towers (IOI22_towers)	C++17	77 / 100	2604 ms	79372 KiB

towers

// correct/solution-prabowo-wavelet.cpp
#include "towers.h"

#include <algorithm>
#include <utility>
#include <vector>

const int kInf = 1e9 + 5;

struct Node {
  int cnt, max, min, maxmin, minmax;
  Node(int val=-1): cnt(1), max(val), min(val), maxmin(-1), minmax(-1) {
    if (val == -1) cnt = 0, max = -1, min = kInf;
  }
};
Node operator + (const Node &p, const Node &q) {
  Node ret;
  ret.cnt = p.cnt + q.cnt;
  ret.max = std::max(p.max, q.max); ret.min = std::min(p.min, q.min);
  ret.maxmin = std::max({p.maxmin, q.maxmin, p.max - q.min});
  ret.minmax = std::max({p.minmax, q.minmax, q.max - p.min});
  return ret;
}

int N;
std::vector<int> H;

std::vector<Node> tree;
Node query(int l, int r) {
  Node lft, rgt;
  for (l = std::max(0, l) + N, r = std::min(N, r) + N; l < r; l >>= 1, r >>= 1) {
    if (l & 1) lft = lft + tree[l++];
    if (r & 1) rgt = tree[--r] + rgt;
  }
  return lft + rgt;
}

class Wavelet {
 private:
  std::vector<std::vector<int>> partitions, pos;
  std::vector<int> alphabet;
  void build(int idx, int l, int r, int ll, int rr, std::vector<std::pair<int, int>> &val) {
    int mid = (l + r) / 2;
    partitions[idx] = {0};
    for (int i = ll; i < rr; ++i) {
      partitions[idx].push_back(partitions[idx].back() + (val[i].first < alphabet[mid]));
      pos[idx].push_back(val[i].second);
    }
    if (l + 1 == r) return;
    int mmid = std::stable_partition(val.begin() + ll, val.begin() + rr, 
        [&](std::pair<int, int> v) { return v.first < alphabet[mid]; }) - val.begin();
    build(idx + 1, l, mid, ll, mmid, val);
    build(idx + (mid - l) * 2, mid, r, mmid, rr, val);
  }

  Node range(int idx, int l, int r, int ll, int rr, int parL, int parR) {
    if (parL == parR || l >= rr || r <= ll) return Node();
    if (l >= ll && r <= rr) {
      Node ret;
      ret.cnt = parR - parL; ret.max = pos[idx][parR - 1]; ret.min = pos[idx][parL];
      return ret;
    }
    int mid = (l + r) / 2;
    return range(idx + 1, l, mid, ll, rr, partitions[idx][parL], partitions[idx][parR]) +
           range(idx + (mid - l) * 2, mid, r, ll, rr, parL - partitions[idx][parL], parR - partitions[idx][parR]);
  }

 public:
  void build(std::vector<int> val) {
    alphabet = val;
    std::sort(alphabet.begin(), alphabet.end());
    alphabet.erase(std::unique(alphabet.begin(), alphabet.end()), alphabet.end());
    std::vector<std::pair<int, int>> valPos(val.size());
    for (int i = 0; i < static_cast<int>(val.size()); ++i) valPos[i] = {val[i], i};
    partitions.resize(alphabet.size() * 2); pos.resize(alphabet.size() * 2);
    build(0, 0, alphabet.size(), 0, val.size(), valPos);
  }

  // Correctly returns (cnt(i), min(i), max(i)) in val[l..r) s.t. a <= val[i] <= b
  Node range(int l, int r, int a, int b) {
    return range(0, 0, alphabet.size(),
        std::lower_bound(alphabet.begin(), alphabet.end(), a) - alphabet.begin(),
        std::upper_bound(alphabet.begin(), alphabet.end(), b) - alphabet.begin(),    
        l, r);
  }
} waveletH, waveletDelta;

void init(int _N, std::vector<int> _H) {
  N = _N; H = _H; tree.resize(N * 2);
  for (int i = 0; i < N; ++i) tree[i + N] = Node(H[i]);
  for (int i = N - 1; i > 0; --i) tree[i] = tree[i * 2] + tree[i * 2 + 1];

  waveletH.build(H);

  std::vector<int> delta(N);
  for (int i = 0; i < N; ++i) {
    delta[i] = kInf;
    int lft = waveletH.range(0, i, 0, H[i] - 1).max, rgt = waveletH.range(i, N, 0, H[i] - 1).min;
    if (lft >= 0) delta[i] = std::min(delta[i], query(lft + 1, i).max - H[i]);
    if (rgt < N) delta[i] = std::min(delta[i], query(i + 1, rgt).max - H[i]);
  }
  
  waveletDelta.build(delta);
}

int max_towers(int L, int R, int D) {
  Node res = waveletDelta.range(L, ++R, D, kInf);
  int cnt = res.cnt, lft = res.min, rgt = res.max;
  if (cnt == 0) { cnt = 1; lft = rgt = waveletH.range(L, R, 0, query(L, R).min).min; }
  cnt += query(L, waveletH.range(L, lft, D + H[lft], kInf).max + 1).minmax >= D;
  cnt += query(waveletH.range(rgt, R, D + H[rgt], kInf).min, R).maxmin >= D;
  return cnt;
}

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