oj.uz

Submission #625604

# Submission time Handle Problem Language Result Execution time Memory
625604 2022-08-10T15:46:39 Z d4xn Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 5104 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>

const int inf = INT_MAX;

int n;
vi v, seg;

void build(int p=1, int l=0, int r=n-1) {
  if (l == r) {
    seg[p] = v[l];
    return;
  }

  int mid = (l+r)/2;
  build(p*2, l, mid);
  build(p*2+1, mid+1, r);
  seg[p] = max(seg[p], seg[p*2]);
}

int query(int a, int b, int p=1, int l=0, int r=n-1) {
  if (a > b || a > r || b < l) return -inf;
  if (a <= l && r <= b) {
    return seg[p];   
  }

  int mid = (l+r)/2;
  int x = query(a, b, p*2, l, mid);
  int y = query(a, b, p*2+1, mid+1, r);
  return max(x, y);
}

void init(int N, std::vector<int> H) {
  n = N;
  seg.resize(n*4);
  v.resize(n);
  for (int i = 0; i < n; i++) v[i] = H[i];
  build();
}

int max_towers(int L, int R, int D) {
  int l = L;
  int r = R;
  int d = D;

  vii s(r-l+1);
  for (int i = l; i <= r; i++) {
    s[i-l] = make_pair(v[i], i);
  }
  sort(s.begin(), s.end());

  set<int> taken;
  for (int i = 0; i < r-l+1; i++) {
    int h = s[i].first;
    int idx = s[i].second;
    
    auto it = taken.upper_bound(idx);
    bool ok = 0;
    if (it != taken.end()) {
      int hi = *it;
      if (h + d <= query(idx+1, hi-1)) ok = 1;
    }
    else ok = 1;

    if (!ok) continue;

    ok = 0;
    if (it != taken.begin() && !taken.empty()) {
      --it;
      int lo = *it;
      if (h + d <= query(lo+1, idx-1)) ok = 1;
    }
    else ok = 1;

    if (ok) taken.insert(idx);
  }
  return taken.size();
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4010 ms 5104 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 4022 ms 1524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

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