oj.uz

답안 #630792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
630792 2022-08-17T03:44:40 Z hltk 송신탑 (IOI22_towers) C++17
0 / 100
 4000 ms 5020 KB 
#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 nxt = added.lower_bound({l, 0});
    if (nxt != added.end() && region_end[nxt->second] <= r) {
      continue;
    } else {
      added.emplace(l, r);
    }
  }
  return added.size();
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4062 ms 2028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4010 ms 5020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4038 ms 1540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4062 ms 2028 KB Time limit exceeded
2 Halted 0 ms 0 KB -