oj.uz

답안 #630793

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
630793 2022-08-17T03:51:27 Z hltk 송신탑 (IOI22_towers) C++17
11 / 100
 4000 ms 3480 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];
    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

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

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 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 1 ms 336 KB Output is correct
15 Correct 1 ms 208 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 336 KB Output is correct
21 Correct 6 ms 336 KB Output is correct
22 Correct 8 ms 464 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 1 ms 208 KB Output is correct
26 Correct 3 ms 336 KB Output is correct
27 Correct 3 ms 336 KB Output is correct
28 Correct 3 ms 336 KB Output is correct
29 Correct 3 ms 336 KB Output is correct
30 Correct 3 ms 336 KB Output is correct
31 Correct 4 ms 336 KB Output is correct
32 Correct 3 ms 320 KB Output is correct
33 Correct 3 ms 328 KB Output is correct
34 Correct 3 ms 324 KB Output is correct
35 Correct 3 ms 336 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 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 1 ms 336 KB Output is correct
15 Correct 1 ms 208 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 336 KB Output is correct
21 Correct 6 ms 336 KB Output is correct
22 Correct 8 ms 464 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 1 ms 208 KB Output is correct
26 Correct 3 ms 336 KB Output is correct
27 Correct 3 ms 336 KB Output is correct
28 Correct 3 ms 336 KB Output is correct
29 Correct 3 ms 336 KB Output is correct
30 Correct 3 ms 336 KB Output is correct
31 Correct 4 ms 336 KB Output is correct
32 Correct 3 ms 320 KB Output is correct
33 Correct 3 ms 328 KB Output is correct
34 Correct 3 ms 324 KB Output is correct
35 Correct 3 ms 336 KB Output is correct
36 Correct 308 ms 1816 KB Output is correct
37 Correct 1549 ms 2648 KB Output is correct
38 Correct 321 ms 2108 KB Output is correct
39 Correct 872 ms 2368 KB Output is correct
40 Correct 202 ms 2204 KB Output is correct
41 Execution timed out 4038 ms 3480 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 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 1 ms 336 KB Output is correct
15 Correct 1 ms 208 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 336 KB Output is correct
21 Correct 6 ms 336 KB Output is correct
22 Correct 8 ms 464 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 1 ms 208 KB Output is correct
26 Correct 3 ms 336 KB Output is correct
27 Correct 3 ms 336 KB Output is correct
28 Correct 3 ms 336 KB Output is correct
29 Correct 3 ms 336 KB Output is correct
30 Correct 3 ms 336 KB Output is correct
31 Correct 4 ms 336 KB Output is correct
32 Correct 3 ms 320 KB Output is correct
33 Correct 3 ms 328 KB Output is correct
34 Correct 3 ms 324 KB Output is correct
35 Correct 3 ms 336 KB Output is correct
36 Correct 308 ms 1816 KB Output is correct
37 Correct 1549 ms 2648 KB Output is correct
38 Correct 321 ms 2108 KB Output is correct
39 Correct 872 ms 2368 KB Output is correct
40 Correct 202 ms 2204 KB Output is correct
41 Execution timed out 4038 ms 3480 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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