Submission #1224510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224510		trimkus	Radio Towers (IOI22_towers)	C++20	0 / 100	317 ms	7292 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
vector<int> a;
vector<int> R, L;
int idx;
int N;
const int MAXN = 2e5;
vector<int> ps;
struct RMQ {
  vector<int> tree;
  int n;
  RMQ(int n) {
    this->n = n;
    tree = vector<int>(4 * n);
  }
  void update(int i, int l, int r, int qp, int val) {
    if (l == r) {
      tree[i] = val;
      return;
    }
    int m = (l + r) / 2;
    if (qp <= m) update(i * 2, l, m, qp, val);
    else update(i * 2 + 1, m + 1, r, qp, val);
    tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
  }
  void update(int qp, int val) {
    update(1, 1, n, qp, val);
  }
  int query(int i, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) {
      return tree[i];
    }
    int m = (l + r) / 2;
    return max(query(i * 2, l, m, ql, qr), query(i * 2 + 1, m + 1, r, ql, qr));
  }
  int query(int ql, int qr) {
    return query(1, 1, n, ql, qr);
  }
} seg(MAXN + 1);
vector<int> req;
void init(int _N, std::vector<int> _H) {
  N = _N;
  a.push_back(0);
  vector<array<int, 2>> ord;
  for (int i = 1; i <= N; ++i) {
    a.push_back(_H[i - 1]);
    seg.update(i, a[i]);
    ord.push_back({a[i], i});
  }
  sort(begin(ord), end(ord));
  set<int> st;
  st.insert(0);
  st.insert(N + 1);
  for (auto [u, i] : ord) {
    auto it = st.lower_bound(i);
    int r = *it;
    --it;
    int l = *it;
    if (l == 0 && r == N + 1) {
        req.push_back(1e9 + 1);
        st.insert(i);
        continue;
    }
    int mxL = 1e9 + 1;
    if (l != 0) {
      mxL = seg.query(l + 1, i - 1) - u;
    }
    int mxR = 1e9 + 1;
    if (r != N + 1) {
      mxR = seg.query(i + 1, r - 1) - u;
    }
    int mx = min(mxR, mxL);
    if (mx <= 0) continue;
    st.insert(i);
    req.push_back(mx);
  }
  sort(begin(req), end(req));
  // for (auto& u : req) {
  //   cerr << u << " ";
  // }
  // cerr << "\n";
}

int max_towers(int l, int r, int D) {
    int i = upper_bound(begin(req), end(req), D) - begin(req);
    i = (int)req.size() - i;
    return i;
}

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