oj.uz

Submission #630794

# Submission time Handle Problem Language Result Execution time Memory
630794 2022-08-17T03:54:34 Z hltk Radio Towers (IOI22_towers) C++17
11 / 100
 4000 ms 3044 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);
  }
  for (int i = l; i < r; ++i) {
    for (int j = i + 1; j < r; ++j) {
      int l1 = region_start[i], r1 = region_end[i];
      int l2 = region_start[j], r2 = region_end[j];
      if (r2 <= l1 || r1 <= l2) {
        continue;
      }
      if (l1 <= l2 && r2 <= r1) {
        continue;
      }
      if (l2 <= l1 && r1 <= r2) {
        continue;
      }
      throw;
    }
  }
  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];
    bool f = 0;
    for (auto [cl, cr] : added) {
      if (cr <= l || r <= cl) {
      } else {
        f = 1;
        break;
      }
    }
    if (!f) {
      added.emplace(l, r);
    }
  }
  return added.size();
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4046 ms 1676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 216 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 3 ms 336 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 4 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 6 ms 368 KB Output is correct
21 Correct 10 ms 388 KB Output is correct
22 Correct 8 ms 336 KB Output is correct
23 Correct 4 ms 336 KB Output is correct
24 Correct 4 ms 336 KB Output is correct
25 Correct 2 ms 208 KB Output is correct
26 Correct 6 ms 336 KB Output is correct
27 Correct 6 ms 336 KB Output is correct
28 Correct 6 ms 336 KB Output is correct
29 Correct 6 ms 336 KB Output is correct
30 Correct 6 ms 336 KB Output is correct
31 Correct 7 ms 336 KB Output is correct
32 Correct 5 ms 336 KB Output is correct
33 Correct 5 ms 336 KB Output is correct
34 Correct 7 ms 336 KB Output is correct
35 Correct 4 ms 336 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 216 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 3 ms 336 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 4 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 6 ms 368 KB Output is correct
21 Correct 10 ms 388 KB Output is correct
22 Correct 8 ms 336 KB Output is correct
23 Correct 4 ms 336 KB Output is correct
24 Correct 4 ms 336 KB Output is correct
25 Correct 2 ms 208 KB Output is correct
26 Correct 6 ms 336 KB Output is correct
27 Correct 6 ms 336 KB Output is correct
28 Correct 6 ms 336 KB Output is correct
29 Correct 6 ms 336 KB Output is correct
30 Correct 6 ms 336 KB Output is correct
31 Correct 7 ms 336 KB Output is correct
32 Correct 5 ms 336 KB Output is correct
33 Correct 5 ms 336 KB Output is correct
34 Correct 7 ms 336 KB Output is correct
35 Correct 4 ms 336 KB Output is correct
36 Correct 522 ms 1720 KB Output is correct
37 Correct 2770 ms 2652 KB Output is correct
38 Correct 551 ms 2104 KB Output is correct
39 Correct 1462 ms 2364 KB Output is correct
40 Correct 377 ms 2268 KB Output is correct
41 Execution timed out 4017 ms 1812 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4042 ms 3044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 1160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 216 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 3 ms 336 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 4 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 6 ms 368 KB Output is correct
21 Correct 10 ms 388 KB Output is correct
22 Correct 8 ms 336 KB Output is correct
23 Correct 4 ms 336 KB Output is correct
24 Correct 4 ms 336 KB Output is correct
25 Correct 2 ms 208 KB Output is correct
26 Correct 6 ms 336 KB Output is correct
27 Correct 6 ms 336 KB Output is correct
28 Correct 6 ms 336 KB Output is correct
29 Correct 6 ms 336 KB Output is correct
30 Correct 6 ms 336 KB Output is correct
31 Correct 7 ms 336 KB Output is correct
32 Correct 5 ms 336 KB Output is correct
33 Correct 5 ms 336 KB Output is correct
34 Correct 7 ms 336 KB Output is correct
35 Correct 4 ms 336 KB Output is correct
36 Correct 522 ms 1720 KB Output is correct
37 Correct 2770 ms 2652 KB Output is correct
38 Correct 551 ms 2104 KB Output is correct
39 Correct 1462 ms 2364 KB Output is correct
40 Correct 377 ms 2268 KB Output is correct
41 Execution timed out 4017 ms 1812 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4046 ms 1676 KB Time limit exceeded
2 Halted 0 ms 0 KB -