oj.uz

Submission #735890

# Submission time Handle Problem Language Result Execution time Memory
735890 2023-05-05T00:23:03 Z math_rabbit_1028 Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 5672 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
 
int n;
vector<int> arr;
int sort_index[101010];
 
 
struct maxseg {
  int tree[404040];
  vector<int> initarr;
  void init(int v, int st, int ed) {
    if (st == ed) {
      tree[v] = initarr[st];
      return;
    }
    int mid = (st + ed) / 2;
    init(2 * v, st, mid);
    init(2 * v + 1, mid + 1, ed);
    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];
  vector<int> initarr;
  void init(int v, int st, int ed) {
    if (st == ed) {
      tree[v] = initarr[st];
      return;
    }
    int mid = (st + ed) / 2;
    init(2 * v, st, mid);
    init(2 * v + 1, mid + 1, ed);
    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;
 
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;
  }
  max_value.initarr = arr;
  right_index.initarr = vector<int>(n, n);
  left_index.initarr = vector<int>(n, -1);
  max_value.init(1, 0, n - 1);
}
 
 
int max_towers(int L, int R, int D) {
  int ans = 0;
  left_index.init(1, 0, n - 1);
  right_index.init(1, 0, n - 1);
 
  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]);
    }
    else break;
  }
  return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4006 ms 3204 KB Time limit exceeded
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: '2'
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: '2'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4030 ms 5672 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 4050 ms 1636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

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: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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