Submission #1248267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248267		aykhn	Radio Towers (IOI22_towers)	C++20	11 / 100	4051 ms	1972 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> arr;

void init(int N, vector<int> H)
{
  n = N, arr = H;
}

int max_towers(int L, int R, int D)
{
  vector<int> l(n), r(n);
  for (int i = 0; i < n; i++)
  {
    l[i] = i - 1, r[i] = i + 1;
    while (l[i] >= 0 && arr[l[i]] - arr[i] < D) l[i]--;
    while (r[i] < n && arr[r[i]] - arr[i] < D) r[i]++;
  }
  int st = L, en = R;
  for (int i = L; i <= R; i++)
  {
    if (r[i] < r[st]) st = i;
  }
  for (int i = R; i >= L; i--)
  {
    if (l[i] > l[en]) en = i;
  }
  if (r[st] > l[en]) return 1;
  int res = 2, prv = st;
  while (1)
  {
    int nxt = -1;
    for (int i = prv + 1; i < en; i++)
    {
      if (!(l[i] >= r[prv] && r[i] <= l[en])) continue;
      if (nxt == -1) nxt = i;
      else if (r[nxt] > r[i]) nxt = i;
    }
    if (nxt == -1) break;
    res++;
    prv = nxt;
  }
  return res;
}

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23