Submission #1035129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035129		NeroZein	Radio Towers (IOI22_towers)	C++17	23 / 100	4093 ms	10080 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std; 

const int LOG = 18; 

int n;
vector<int> h;
vector<int> spa[LOG];

int get_max(int l, int r) {
  int lg = 31 - __builtin_clz(r - l + 1);
  return max(spa[lg][l], spa[lg][r - (1 << lg) + 1]);
}

void init(int N_, vector<int> H_) {
  n = N_, h = H_;
  spa[0] = h;
  for (int j = 1; (1 << j) <= n && j < LOG; ++j) {
    spa[j].resize(n - (1 << j) + 1); 
    for (int i = 0; i + (1 << j) <= n; ++i) {
      spa[j][i] = max(spa[j - 1][i], spa[j - 1][i + (1 << (j - 1))]);
    }
  }
}

int max_towers(int l, int r, int d) {
  vector<int> ord;
  for (int i = l; i <= r; ++i) {
    ord.push_back(i); 
  }
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return h[i] < h[j];
  });
  set<int> se; 
  for (int i : ord) {
    auto it = se.lower_bound(i);
    bool ok = true;
    if (it != se.end()) {
      int nxt = *it; 
      if (nxt == i + 1 || get_max(i + 1, nxt - 1) < h[i] + d) {
        ok = false; 
      }
    }
    if (it != se.begin()) {
      int pre = *prev(it); 
      if (pre == i - 1 || get_max(pre + 1, i - 1) < h[i] + d) {
        ok = false; 
      }
    }
    if (ok) {
      se.insert(i); 
    }
  }
  return (int) se.size();
}

• 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