Submission #625633

#	Time	Username	Problem	Language	Result	Execution time	Memory
625633		d4xn	Radio Towers (IOI22_towers)	C++17	27 / 100	4094 ms	5864 KiB

towers

#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) {
    if (l <= s1 && s1 <= r) {
      return (max(v[l], v[r]) + d <= v[s1] ? 2 : 1);
    }
    return 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: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23