Submission #1073646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073646		fv3	Radio Towers (IOI22_towers)	C++17	23 / 100	544 ms	6600 KiB

towers

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

using namespace std;
const int INF = 1 << 30;

int N;
vector<int> H;

struct node
{
  int mn;
  int index;
};
node merge(const node a, const node b)
{
  return a.mn < b.mn ? a : b;
}
const node empty_node = {INF, 0};

int nt;
vector<int> st_mx;
vector<node> st_mn;

node get_min_range(int l, int r, int k, int tl, int tr)
{
  if (tr < l || tl > r) return empty_node;
  if (tl >= l && tr <= r) return st_mn[k];
  int c = (tl + tr) / 2;
  return merge(get_min_range(l, r, k*2, tl, c), get_min_range(l, r, k*2|1, c+1, tr));
}

void set_min(int i)
{
  i += nt;
  st_mn[i] = empty_node;
  for (i /= 2; i >= 1; i /= 2)
    st_mn[i] = merge(st_mn[i*2], st_mn[i*2|1]);
}

int get_max_range(int l, int r, int k, int tl, int tr)
{
  if (tr < l || tl > r) return 0;
  if (tl >= l && tr <= r) return st_mx[k];
  int c = (tl + tr) / 2;
  return max(get_max_range(l, r, k*2, tl, c), get_max_range(l, r, k*2|1, c+1, tr));
}

void init(int N_, vector<int> H_)
{
  N = N_;
  H = H_;

  nt = 1;
  while (nt < N) nt <<= 1;

  st_mx = vector<int>(nt*2);
  st_mn = vector<node>(nt*2, empty_node);

  for (int i = 0; i < N; i++)
  {
    st_mx[nt + i] = H[i];
    st_mn[nt + i] = {H[i], i};
  }

  for (int i = nt - 1; i >= 1; i--)
  {
    st_mx[i] = max(st_mx[i*2], st_mx[i*2|1]);
    st_mn[i] = merge(st_mn[i*2], st_mn[i*2|1]); 
  }
}

int max_towers(int L, int R, int D) 
{
  // You should always lease the smallest tower
  // No two adjacent towers can be leased

  int res = 0;
  set<int> leased;
  while (true)
  {
    node cnd = get_min_range(L, R, 1, 0, nt - 1);
    if (cnd.mn == INF) break;
    if (!leased.size())
    {
      res++;
      leased.insert(cnd.index);
      for (int i = max(L, cnd.index-1); i <= min(R, cnd.index + 1); i++)
        set_min(i);
      continue;
    }

    if (*leased.begin() < cnd.index)
    {
      int l = *--leased.lower_bound(cnd.index);
      int mx = get_max_range(l, cnd.index, 1, 0, nt - 1);

      if (mx - cnd.mn < D)
      {
        set_min(cnd.index);
        continue;
      }
    }
    if (*--leased.end() > cnd.index)
    {
      int r = *leased.lower_bound(cnd.index);
      int mx = get_max_range(cnd.index, r, 1, 0, nt - 1);

      if (mx - cnd.mn < D)
      {
        set_min(cnd.index);
        continue;
      }
    }
 
    res++;
    leased.insert(cnd.index);
    for (int i = max(L, cnd.index-1); i <= min(R, cnd.index + 1); i++)
      set_min(i);
  }

  return res;
}

• Subtask 1: 0 / 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