Submission #1223882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223882		trimkus	Radio Towers (IOI22_towers)	C++20	23 / 100	4075 ms	7244 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;
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);

void init(int _N, std::vector<int> _H) {
  N = _N;
  a.push_back(0);
  for (int i = 1; i <= N; ++i) {
    a.push_back(_H[i - 1]);
    seg.update(i, a[i]);
  }
}

int max_towers(int l, int r, int D) {
    l += 1;
    r += 1;
    set<int> st;
    st.insert(0);
    st.insert(N + 1);
    vector<array<int, 2>> pos;
    for (int i = l; i <= r; ++i) {
      pos.push_back({a[i], i});
    }
    sort(begin(pos), end(pos));
    for (auto [v, i] : pos) {
      auto it = st.lower_bound(i);
      int r = *it;
      --it;
      int l = *it;
      if ((l == 0 || seg.query(l + 1, i - 1) >= v + D)
      && (r == N + 1 || seg.query(i + 1, r - 1) >= v + D)) {
        st.insert(i);
      }
    }
    return (int)st.size() - 2;
}

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