oj.uz

Submission #625454

# Submission time Handle Problem Language Result Execution time Memory
625454 2022-08-10T12:05:09 Z model_code Radio Towers (IOI22_towers) C++17
17 / 100
 1391 ms 18036 KB 
// 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 344 ms 10504 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 910 ms 17728 KB 1st lines differ - on the 1st token, expected: '11903', found: '33010'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 4440 KB Output is correct
2 Correct 887 ms 17904 KB Output is correct
3 Correct 979 ms 17900 KB Output is correct
4 Correct 1060 ms 18036 KB Output is correct
5 Correct 1085 ms 17940 KB Output is correct
6 Correct 1391 ms 17956 KB Output is correct
7 Correct 1073 ms 17872 KB Output is correct
8 Correct 1145 ms 17488 KB Output is correct
9 Correct 1020 ms 17452 KB Output is correct
10 Correct 1068 ms 17452 KB Output is correct
11 Correct 1039 ms 17472 KB Output is correct
12 Correct 134 ms 17912 KB Output is correct
13 Correct 205 ms 17972 KB Output is correct
14 Correct 131 ms 17940 KB Output is correct
15 Correct 91 ms 17428 KB Output is correct
16 Correct 99 ms 17476 KB Output is correct
17 Correct 128 ms 17060 KB Output is correct
18 Correct 140 ms 17832 KB Output is correct
19 Correct 132 ms 17812 KB Output is correct
20 Correct 136 ms 17896 KB Output is correct
21 Correct 130 ms 17948 KB Output is correct
22 Correct 147 ms 17896 KB Output is correct
23 Correct 126 ms 17900 KB Output is correct
24 Correct 92 ms 17452 KB Output is correct
25 Correct 91 ms 17420 KB Output is correct
26 Correct 98 ms 17508 KB Output is correct
27 Correct 87 ms 17512 KB Output is correct
28 Correct 3 ms 592 KB Output is correct
29 Correct 3 ms 592 KB Output is correct
30 Correct 2 ms 592 KB Output is correct
31 Correct 1 ms 580 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 3 ms 592 KB Output is correct
35 Correct 2 ms 640 KB Output is correct
36 Correct 3 ms 592 KB Output is correct
37 Correct 3 ms 592 KB Output is correct
38 Correct 2 ms 592 KB Output is correct
39 Correct 2 ms 612 KB Output is correct
40 Correct 1 ms 592 KB Output is correct
41 Correct 2 ms 592 KB Output is correct
42 Correct 1 ms 592 KB Output is correct
43 Correct 2 ms 592 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 344 ms 10504 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -