oj.uz

Submission #735310

# Submission time Handle Problem Language Result Execution time Memory
735310 2023-05-04T00:29:25 Z math_rabbit_1028 Radio Towers (IOI22_towers) C++17
11 / 100
 4000 ms 9404 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> arr;
int sort_index[101010];
void init(int N, vector<int> H) {
  n = N;
  vector< pair<int, int> > temp;
  for (int i = 0; i < N; i++) arr.push_back(H[i]);
  for (int i = 0; i < N; i++) temp.push_back({H[i], i});
  sort(temp.begin(), temp.end());
  for (int i = 0; i < N; i++) {
    sort_index[i] = temp[i].second;
  }
}

struct maxseg {
  int tree[404040];
  void init(int v, int st, int ed, vector<int> val) {
    if (st == ed) {
      tree[v] = val[st];
      return;
    }
    int mid = (st + ed) / 2;
    init(2 * v, st, mid, val);
    init(2 * v + 1, mid + 1, ed, val);
    tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  }
  void update(int v, int st, int ed, int idx, int val) {
    if (idx < st || idx > ed) return;
    if (idx == st && idx == ed) {
      tree[v] = val;
      return;
    }
    int mid = (st + ed) / 2;
    update(2 * v, st, mid, idx, val);
    update(2 * v + 1, mid + 1, ed, idx, val);
    tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  }
  int get(int v, int st, int ed, int gs, int ge) {
    if (st > ge || ed < gs) return -1;
    if (gs <= st && ed <= ge) return tree[v];
    int mid = (st + ed) / 2;
    return max(get(2 * v, st, mid, gs, ge), get(2 * v + 1, mid + 1, ed, gs, ge));
  }
} max_value, left_index;

struct minseg {
  int tree[404040];
  void init(int v, int st, int ed, vector<int> val) {
    if (st == ed) {
      tree[v] = val[st];
      return;
    }
    int mid = (st + ed) / 2;
    init(2 * v, st, mid, val);
    init(2 * v + 1, mid + 1, ed, val);
    tree[v] = min(tree[2 * v], tree[2 * v + 1]);
  }
  void update(int v, int st, int ed, int idx, int val) {
    if (idx < st || idx > ed) return;
    if (idx == st && idx == ed) {
      tree[v] = val;
      return;
    }
    int mid = (st + ed) / 2;
    update(2 * v, st, mid, idx, val);
    update(2 * v + 1, mid + 1, ed, idx, val);
    tree[v] = min(tree[2 * v], tree[2 * v + 1]);
  }
  int get(int v, int st, int ed, int gs, int ge) {
    if (st > ge || ed < gs) return n;
    if (gs <= st && ed <= ge) return tree[v];
    int mid = (st + ed) / 2;
    return min(get(2 * v, st, mid, gs, ge), get(2 * v + 1, mid + 1, ed, gs, ge));
  }
} right_index;

int max_towers(int L, int R, int D) {
  int ans = 0;
  left_index.init(1, 0, n - 1, vector<int>(n, -1));
  max_value.init(1, 0, n - 1, arr);
  right_index.init(1, 0, n - 1, vector<int>(n, n));

  for (int i = 0; i < n; i++) {
    if (sort_index[i] < L || sort_index[i] > R) continue;
    bool f = true;

    int j = right_index.get(1, 0, n - 1, sort_index[i] + 1, R);
    //cout << sort_index[i] << " " << j << "\n";
    if (j >= 0 && j < n)
      if (max_value.get(1, 0, n - 1, sort_index[i] + 1, j - 1) < max(arr[sort_index[i]], arr[j]) + D) 
        f = false;
    j = left_index.get(1, 0, n - 1, L, sort_index[i] - 1);
    //cout << j << " " << sort_index[i] << "\n";  
    if (j >= 0 && j < n)
      if (max_value.get(1, 0, n - 1, j + 1, sort_index[i] - 1) < max(arr[sort_index[i]], arr[j]) + D) 
        f = false;

    if (f) {
      ans++;
      left_index.update(1, 0, n - 1, sort_index[i], sort_index[i]);
      right_index.update(1, 0, n - 1, sort_index[i], sort_index[i]);
    }
  }
  return ans;
}

Subtask #1
0 / 4.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 5 ms 464 KB Output is correct
3 Correct 5 ms 476 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 4 ms 464 KB Output is correct
6 Correct 4 ms 500 KB Output is correct
7 Correct 6 ms 464 KB Output is correct
8 Correct 4 ms 464 KB Output is correct
9 Correct 7 ms 464 KB Output is correct
10 Correct 8 ms 464 KB Output is correct
11 Correct 7 ms 464 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 5 ms 464 KB Output is correct
14 Correct 5 ms 464 KB Output is correct
15 Correct 4 ms 464 KB Output is correct
16 Correct 5 ms 464 KB Output is correct
17 Correct 4 ms 464 KB Output is correct
18 Correct 4 ms 464 KB Output is correct
19 Correct 5 ms 464 KB Output is correct
20 Correct 7 ms 464 KB Output is correct
21 Correct 5 ms 464 KB Output is correct
22 Correct 5 ms 464 KB Output is correct
23 Correct 7 ms 464 KB Output is correct
24 Correct 4 ms 464 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 5 ms 464 KB Output is correct
27 Correct 5 ms 464 KB Output is correct
28 Correct 5 ms 464 KB Output is correct
29 Correct 5 ms 464 KB Output is correct
30 Correct 5 ms 476 KB Output is correct
31 Correct 5 ms 464 KB Output is correct
32 Correct 5 ms 484 KB Output is correct
33 Correct 5 ms 464 KB Output is correct
34 Correct 4 ms 464 KB Output is correct
35 Correct 7 ms 464 KB Output is correct
36 Execution timed out 4067 ms 6136 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4005 ms 9404 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 4041 ms 3052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 5 ms 464 KB Output is correct
3 Correct 5 ms 476 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 4 ms 464 KB Output is correct
6 Correct 4 ms 500 KB Output is correct
7 Correct 6 ms 464 KB Output is correct
8 Correct 4 ms 464 KB Output is correct
9 Correct 7 ms 464 KB Output is correct
10 Correct 8 ms 464 KB Output is correct
11 Correct 7 ms 464 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 5 ms 464 KB Output is correct
14 Correct 5 ms 464 KB Output is correct
15 Correct 4 ms 464 KB Output is correct
16 Correct 5 ms 464 KB Output is correct
17 Correct 4 ms 464 KB Output is correct
18 Correct 4 ms 464 KB Output is correct
19 Correct 5 ms 464 KB Output is correct
20 Correct 7 ms 464 KB Output is correct
21 Correct 5 ms 464 KB Output is correct
22 Correct 5 ms 464 KB Output is correct
23 Correct 7 ms 464 KB Output is correct
24 Correct 4 ms 464 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 5 ms 464 KB Output is correct
27 Correct 5 ms 464 KB Output is correct
28 Correct 5 ms 464 KB Output is correct
29 Correct 5 ms 464 KB Output is correct
30 Correct 5 ms 476 KB Output is correct
31 Correct 5 ms 464 KB Output is correct
32 Correct 5 ms 484 KB Output is correct
33 Correct 5 ms 464 KB Output is correct
34 Correct 4 ms 464 KB Output is correct
35 Correct 7 ms 464 KB Output is correct
36 Execution timed out 4067 ms 6136 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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