Submission #630796

#	Time	Username	Problem	Language	Result	Execution time	Memory
630796		hltk	Radio Towers (IOI22_towers)	C++17	11 / 100	4088 ms	4928 KiB

towers

#include "towers.h"

#include <vector>
#include <set>
#include <iostream>
#include <queue>

using namespace std;

// The key observation.
//  - All towers have a 'banned region' that spans some elements
//    on both sides of the tower. It ends to either to the end
//    of the array, or to the next element with height larger
//    by at least D.
//
// Some further observations on 'banned regions'.
//  - If a tower is selected, no other towers from its banned
//    region may be selected. Thus, we need to select the
//    maximum amount of towers such that none of their banned
//    regions overlap.
//  - A region may be completely contained in a another. Let us
//    ignore this case from now on.
//  - Any two regions, that are not contained in each other, will not
//    intersect at any point other than an optional shared endpoint,
//    and because regions with a shared endpoint may be selected,
//    we will have to find the amount of regions when completely
//    contained regions are removed.
//  - If a region is contained inside another, it is optimal to remove
//    the larger only of them. If the ranges are exactly the same,
//    we will remove the one with a lower value of h[i].
//
// Ideas for the full solution.
//  - Let us first try to solve the problem for a fixed
//    value of D.
//  - We need to be able to efficiently answer range
//    queries, that is, we need to be able find the maximum amount
//    non-contained regions in a range.
//     - One solution, that is also easily made persistent, is
//       to use two segments trees. One for finding the first range,
//       and the other for finding the amount of ranges (by for example,
//       counting endpoints of ranges in the tree).
//  - Now it's pretty easy to generalize this for all values of D.
//  - Let us sweep through values of D.
//  - An increase in the value of D, can cause some ranges to lengthen.
//  - It may happen that when a range lengthens it 'eats' another range
//    inside of it, which makes it redundant.
//  - Let us start with D = 1 and the largest possible set of
//    non-contained ranges.
//  - We have to account for the 'eating' of regions, while keeping
//    track of the ranges.
//  - At any point, the amount of regions in a query range, is the answer
//    to the range query.
//  - One more important observation. The optimal set of regions forms
//    a continuous chain, which makes it easy to maintain as any
//    lengthening will cause ranges to 'eat' each other, and thus
//    cause a removal.

int n;
vector<int> h;

void init(int n, vector<int> h) {
  ::n = n;
  ::h = h;
}

int max_towers(int l, int r, int d) {
  r++;
  vector<int> region_start(n), region_end(n);
  for (int i = l; i < r; ++i) {
    region_start[i] = i;
    while (region_start[i] >= 0 && h[region_start[i]] < h[i] + d) {
      region_start[i]--;
    }
    region_start[i] = max(region_start[i], l);
    region_end[i] = i;
    while (region_end[i] < r && h[region_end[i]] < h[i] + d) {
      region_end[i]++;
    }
    region_end[i] = min(region_end[i], r - 1);
  }
  priority_queue<pair<int, int>> ranges;
  for (int i = l; i < r; ++i) {
    ranges.emplace(region_start[i] - region_end[i], i);
  }
  set<pair<int, int>> added;
  while (!ranges.empty()) {
    int i = ranges.top().second;
    ranges.pop();
    int l = region_start[i], r = region_end[i];
    auto it = added.lower_bound({l, 0});
    if (!(it != added.end() && it->second <= r)) {
      added.emplace(l, r);
    }
  }
  return added.size();
}

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