Submission #1248268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248268		aykhn	Radio Towers (IOI22_towers)	C++20	100 / 100	1255 ms	41248 KiB

towers

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

using namespace std;

#define inf 0x3F3F3F3F

const int MXN = 1e5 + 5;
const int LOG = 17;

struct DATA
{
  int l = -1, r = -1, sum = 0;
};

int n;
vector<int> arr;
vector<int> prv, nxt;
int mx[LOG][MXN];
int LG[MXN];
int d[MXN];
vector<int> mpd;
vector<int> q[MXN];
int nd, root[MXN];
DATA st[MXN * (LOG + 4)];
array<int, 4> st1[MXN << 2];

array<int, 4> combine(array<int, 4> x, array<int, 4> y)
{
  return {min(x[0], y[0]), max(x[1], y[1]), max({x[2], y[2], y[1] - x[0]}), max({x[3], y[3], x[1] - y[0]})};
}
void build(int l, int r, int x)
{
  if (l == r)
  {
    st1[x] = {arr[l], arr[l], 0, 0};
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, 2*x);
  build(mid + 1, r, 2*x + 1);
  st1[x] = combine(st1[2*x], st1[2*x + 1]);
}
array<int, 4> getd(int l, int r, int x, int lx, int rx)
{
  if (l > rx || r < lx) return {inf, -inf, 0, 0};
  if (l >= lx && r <= rx) return st1[x];
  int mid = (l + r) >> 1;
  return combine(getd(l, mid, 2*x, lx, rx), getd(mid + 1, r, 2*x + 1, lx, rx));
}
int build(int l, int r)
{
  int nw = nd++;
  if (l == r) 
  {
    st[nw].sum = 1;
    return nw;
  }
  int mid = (l + r) >> 1;
  st[nw].l = build(l, mid);
  st[nw].r = build(mid + 1, r);
  st[nw].sum = st[st[nw].l].sum + st[st[nw].r].sum;
  return nw;
}
int upd(int l, int r, int x, int ind)
{
  int nw = nd++;
  st[nw] = st[x];
  if (l == r)
  {
    st[nw].sum = 0;
    return nw;
  }
  int mid = (l + r) >> 1;
  if (ind <= mid) st[nw].l = upd(l, mid, st[x].l, ind);
  else st[nw].r = upd(mid + 1, r, st[x].r, ind);
  st[nw].sum = st[st[nw].l].sum + st[st[nw].r].sum;
  return nw;
}
int get(int l, int r, int x, int lx, int rx)
{
  if (l > rx || r < lx) return 0;
  if (l >= lx && r <= rx) return st[x].sum;
  int mid = (l + r) >> 1;
  return get(l, mid, st[x].l, lx, rx) + get(mid + 1, r, st[x].r, lx, rx);
}

int getmx(int l, int r)
{
  if (l > r) return 0;
  int lg = LG[r - l + 1];
  return max(mx[lg][l], mx[lg][r - (1 << lg) + 1]);
}

void init(int N, vector<int> H)
{
  n = N, arr = H;
  prv.assign(n, -1), nxt.assign(n, n);
  LG[1] = 0;
  for (int i = 2; i < MXN; i++) LG[i] = LG[i >> 1] + 1;
  {
    vector<int> v;
    for (int i = 0; i < n; i++)
    {
      while (!v.empty() && arr[v.back()] > arr[i]) v.pop_back();
      prv[i] = (v.empty() ? -1 : v.back());
      v.push_back(i);
    }
  }
  {
    vector<int> v;
    for (int i = n - 1; i >= 0; i--)
    {
      while (!v.empty() && arr[v.back()] > arr[i]) v.pop_back();
      nxt[i] = (v.empty() ? n : v.back());
      v.push_back(i);
    }
  }
  for (int i = 0; i < n; i++) mx[0][i] = arr[i];
  for (int i = 1; i < LOG; i++) for (int j = 0; j + (1 << i) - 1 < n; j++) mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
  mpd = {0};
  for (int i = 0; i < n; i++)
  {
    d[i] = min(getmx(prv[i] + 1, i - 1), getmx(i + 1, nxt[i] - 1)) - arr[i];
    d[i] = max(0, d[i]);
    mpd.push_back(d[i] + 1);
  }
  sort(mpd.begin(), mpd.end());
  mpd.resize(unique(mpd.begin(), mpd.end()) - mpd.begin());
  for (int i = 0; i < n; i++)
  {
    int ind = lower_bound(mpd.begin(), mpd.end(), d[i] + 1) - mpd.begin();
    q[ind].push_back(i);
  }
  root[0] = build(0, n - 1);
  for (int i = 1; i < mpd.size(); i++) 
  {
    root[i] = root[i - 1];
    for (int &j : q[i]) root[i] = upd(0, n - 1, root[i], j);
  }
  build(0, n - 1, 1);
}

int max_towers(int L, int R, int D)
{
  int ind = upper_bound(mpd.begin(), mpd.end(), D) - mpd.begin() - 1;
  int st = -1, en = -1;
  {
    int lx = L, rx = R + 1;
    while (lx < rx)
    {
      int mid = (lx + rx) >> 1;
      if (getd(0, n - 1, 1, L, mid)[2] >= D) rx = mid;
      else lx = mid + 1;
    }
    if (lx == R + 1) return 1;
    st = lx;
  }
  {
    int lx = L - 1, rx = R;
    while (lx < rx)
    {
      int mid = (lx + rx + 1) >> 1;
      if (getd(0, n - 1, 1, mid, R)[3] >= D) lx = mid;
      else rx = mid - 1;
    }
    if (lx == L - 1) return 1;
    en = lx;
  }
  if (st > en) return 1;
  int res = 2 + get(0, n - 1, root[ind], st + 1, en - 1);
  return res;
}

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