Submission #625454

#	Time	Username	Problem	Language	Result	Execution time	Memory
625454		model_code	Radio Towers (IOI22_towers)	C++17	17 / 100	1391 ms	18036 KiB

towers

// incorrect/solution-ayaze-full-interval.cpp
#include "towers.h"

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

const int kLogN = 17;
const int kInf = 2'000'000'000;

vector<int> D_bounds;

void init(int N, std::vector<int> H) {
  vector<pair<int, int>> ordered_H;
  for (int i = 0 ; i < N ; i++) {
    ordered_H.push_back({H[i], i});
  }
  sort(ordered_H.begin(), ordered_H.end());

  vector<int> left_lower(N, -1), right_lower(N, -1);
  set<int> active;
  for (auto [_, i] : ordered_H) {
    {
      auto it = active.lower_bound(i);
      if (it != active.begin()) {
        it--;
        left_lower[i] = *it;
      }
    }
    {
      auto it = active.upper_bound(i);
      if (it != active.end()) {
        right_lower[i] = *it;
      }
    }
    active.insert(i);
  }

  vector<vector<int>> sparse_table(N, vector<int>(kLogN, -1));
  for (int i = 0 ; i < N ; i++) {
    sparse_table[i][0] = H[i];
  }
  for (int j = 1 ; j < kLogN ; j++) {
    for (int i = 0 ; i < N ; i++) {
      if (i + (1 << (j-1)) < N) {
        sparse_table[i][j] = max(sparse_table[i][j-1], sparse_table[i + (1 << (j-1))][j-1]);
      }
    }
  }
  function<int(int, int)> queryMax = [&](int l, int r) -> int {
    int lg = 0;
    while (l + (1 << lg) - 1 <= r) lg++;
    lg--;
    return max(sparse_table[l][lg], sparse_table[r - (1 << lg) + 1][lg]);
  };

  for (int i = 0 ; i < N ; i++) {
    int D_max_left = kInf, D_max_right = kInf;
    
    if (left_lower[i] != -1) {
      D_max_left = -1;
      int mx = queryMax(left_lower[i], i);
      D_max_left = mx - H[i];
    }
    if (right_lower[i] != -1) {
      D_max_right = -1;
      int mx = queryMax(i, right_lower[i]);
      D_max_right = mx - H[i];
    }

    int D_max = min(D_max_left, D_max_right);
    if (D_max > 0) {
      D_bounds.push_back(D_max);
    }
  }
  
  sort(D_bounds.begin(), D_bounds.end());
}

int max_towers(int, int, int D) {
  return D_bounds.end() - lower_bound(D_bounds.begin(), D_bounds.end(), 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