oj.uz

Submission #625623

# Submission time Handle Problem Language Result Execution time Memory
625623 2022-08-10T16:08:29 Z d4xn Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 5136 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, s1;
vi v, seg;

void build(int p=1, int l=0, int r=n-1) {
  if (l > r) return;
  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*2], seg[p*2+1]);
}

int query(int a, int b, int p=1, int l=0, int r=n-1) {
  if (l > r || 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();

  s1 = -1;
  bool b = 1;
  for (int i = 1; i < n; i++) {
    if (v[i] > v[i-1]) continue;
    s1 = i-1;
    for (int j = i+1; j < n; j++) {
      if (v[j] > v[j-1]) {
        b = 0;
        break;
      }
    }
    break;
  }
  if (!b) s1 = -1;
  else if (b && s1 == -1) s1 = n-1;
}

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

  if (s1 != -1) {
    return (max(v[0], v[n-1]) + d <= v[s1] ? 2 : 1);
  }

  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 Incorrect 246 ms 1872 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 Correct 1 ms 208 KB Output is correct
2 Correct 1 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 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 284 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
14 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 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 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 284 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4003 ms 5136 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 4018 ms 1664 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 208 KB Output is correct
2 Correct 1 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 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 284 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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