Submission #632408

#	Time	Username	Problem	Language	Result	Execution time	Memory
632408		lunchbox	Radio Towers (IOI22_towers)	C++17	100 / 100	1396 ms	37952 KiB

towers

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
  #include "lib/debug.h"
#else
  #define debug(...) 0
#endif

typedef vector<int> vi;

const int N = 1e5, INF = 1e9 + 1;

template<typename Tp, int N>
struct Rmq_mn {
  static const int L = __lg(N - 1) + 1;
  Tp ar[1 << L], t[L][1 << L];

  Tp op(Tp l, Tp r) {
    return min(l, r);
  }
  void bld(int n, Tp *ar_) {
    int h = n == 1 ? 0 : __lg(n - 1) + 1;
    for (int i = 0; i < 1 << h; i++)
      ar[i] = i < n ? ar_[i] : Tp();
    bld(0, (1 << h) - 1, h - 1);
  }
  void bld(int l, int r, int h) {
    if (h >= 0) {
      int m = (l + r) / 2;
      for (int i = m; i >= l; i--)
        t[h][i] = i == m ? ar[i] : op(ar[i], t[h][i + 1]);
      for (int i = m + 1; i <= r; i++)
        t[h][i] = i == m + 1 ? ar[i] : op(t[h][i - 1], ar[i]);
      bld(l, m, h - 1), bld(m + 1, r, h - 1);
    }
  }
  Tp qry(int l, int r) {
    if (l > r)
      return INT_MAX;
    if (l == r)
      return ar[l];
    int h = __lg(l ^ r);
    return op(t[h][l], t[h][r]);
  }
};

template<typename Tp, int N>
struct Rmq_mx {
  static const int L = __lg(N - 1) + 1;
  Tp ar[1 << L], t[L][1 << L];
  int n;

  Tp op(Tp l, Tp r) {
    return max(l, r);
  }
  void bld(int n_, Tp *ar_) {
    n = n_;
    int h = n == 1 ? 0 : __lg(n - 1) + 1;
    for (int i = 0; i < 1 << h; i++)
      ar[i] = i < n ? ar_[i] : Tp();
    bld(0, (1 << h) - 1, h - 1);
  }
  void bld(int l, int r, int h) {
    if (h >= 0) {
      int m = (l + r) / 2;
      for (int i = m; i >= l; i--)
        t[h][i] = i == m ? ar[i] : op(ar[i], t[h][i + 1]);
      for (int i = m + 1; i <= r; i++)
        t[h][i] = i == m + 1 ? ar[i] : op(t[h][i - 1], ar[i]);
      bld(l, m, h - 1), bld(m + 1, r, h - 1);
    }
  }
  Tp qry(int l, int r) {
    l = max(l, 0);
    r = min(r, n - 1);
    if (l > r)
      return INT_MIN;
    if (l == r)
      return ar[l];
    int h = __lg(l ^ r);
    return op(t[h][l], t[h][r]);
  }
};

int n, u[N], v[N], v1[N + 1];
vi h;
Rmq_mx<int, N> rmq;

namespace s1 {
  const int N_ = N * 18;
  int s[N_], lc[N_], rc[N_], cnt = 0;
  int cp(int k) {
    int q = ++cnt;
    s[q] = s[k], lc[q] = lc[k], rc[q] = rc[k];
    return q;
  }
  void upd(int& k, int l, int r, int i) {
    k = cp(k);
    s[k]++;
    if (l != r) {
      int m = (l + r) / 2;
      if (i <= m)
        upd(lc[k], l, m, i);
      else
        upd(rc[k], m + 1, r, i);
    }
  }
  int sm(int k, int l, int r, int ql, int qr) {
    if (k == 0 || s[k] == 0 || ql > r || qr < l)
      return 0;
    if (ql <= l && qr >= r)
      return s[k];
    int m = (l + r) / 2;
    return sm(lc[k], l, m, ql, qr) + sm(rc[k], m + 1, r, ql, qr);
  }
  int gl(int k, int l, int r, int i) {
    if (l > i || s[k] == 0)
      return -1;
    if (l == r)
      return l;
    int m = (l + r) / 2, p = gl(rc[k], m + 1, r, i);
    return p != -1 ? p : gl(lc[k], l, m, i);
  }
  int gr(int k, int l, int r, int i) {
    if (r < i || s[k] == 0)
      return -1;
    if (l == r)
      return l;
    int m = (l + r) / 2, p = gr(lc[k], l, m, i);
    return p != -1 ? p : gr(rc[k], m + 1, r, i);
  }
  void print(int k, int l, int r) {
    if (k == 0)
      return;
    if (l == r) {
      cout << l << ' ';
      return;
    }
    int m = (l + r) / 2;
    print(lc[k], l, m), print(rc[k], m + 1, r);
  }
};
namespace s2 {
  struct V {
    int a, b, c;
  } s[N * 4], T = {INF, 0, 0};

  V op(V l, V r) {
    return {min(l.a, r.a), max(l.b, r.b), max(r.b - l.a, max(l.c, r.c))};
  }
  void bld() {
    for (int i = 0; i < n; i++)
      s[n + i] = {h[i], h[i], 0};
    for (int i = n - 1; i > 0; i--)
      s[i] = op(s[i * 2], s[i * 2 + 1]);
  }
  int qry(int l, int r) {
    V la = T, ra = T;
    for (l += n, r += n; l <= r; l /= 2, r /= 2) {
      if (l % 2 == 1)
        la = op(la, s[l++]);
      if (r % 2 == 0)
        ra = op(s[r--], ra);
    }
    return op(la, ra).c;
  }
  int val(int l, int r) {
    int x = INF;
    for (l += n, r += n; l <= r; l /= 2, r /= 2) {
      if (l % 2 == 1)
        x = min(x, s[l++].a);
      if (r % 2 == 0)
        x = min(x, s[r--].a);
    }
    return x;
  }
};
namespace s3 {
  struct V {
    int a, b, c;
  } s[N * 4], T = {INF, 0, 0};

  V op(V l, V r) {
    return {min(l.a, r.a), max(l.b, r.b), max(l.b - r.a, max(l.c, r.c))};
  }
  void bld() {
    for (int i = 0; i < n; i++)
      s[n + i] = {h[i], h[i], 0};
    for (int i = n - 1; i > 0; i--)
      s[i] = op(s[i * 2], s[i * 2 + 1]);
  }
  int qry(int l, int r) {
    V la = T, ra = T;
    for (l += n, r += n; l <= r; l /= 2, r /= 2) {
      if (l % 2 == 1)
        la = op(la, s[l++]);
      if (r % 2 == 0)
        ra = op(s[r--], ra);
    }
    return op(la, ra).c;
  }
  int val(int l, int r) {
    int x = INF;
    for (l += n, r += n; l <= r; l /= 2, r /= 2) {
      if (l % 2 == 1)
        x = min(x, s[l++].a);
      if (r % 2 == 0)
        x = min(x, s[r--].a);
    }
    return x;
  }
};

void init(int n_, vi h_) {
  n = n_;
  h = h_;
  rmq.bld(n, h.data());
  vi s;
  fill(v, v + n, INF);
  for (int i = 0; i < n; i++) {
    while (!s.empty() && h[s.back()] >= h[i])
      s.pop_back();
    if (!s.empty())
      v[i] = min(v[i], rmq.qry(s.back(), i) - h[i]);
    s.push_back(i);
  }
  s.clear();
  for (int i = n - 1; i >= 0; i--) {
    while (!s.empty() && h[s.back()] >= h[i])
      s.pop_back();
    if (!s.empty())
      v[i] = min(v[i], rmq.qry(i, s.back()) - h[i]);
    s.push_back(i);
  }
  s.clear();
  iota(u, u + n, 0);
  sort(u, u + n, [&](int i, int j) {
    return v[i] > v[j];
  });
  v1[0] = 0;
  for (int i = 0; i < n; i++) {
    v1[i + 1] = v1[i];
    s1::upd(v1[i + 1], 0, n - 1, u[i]);
  }
  s2::bld();
  s3::bld();
}

int Gl(int i, int d) {
  if (rmq.qry(1, i) < h[i] + d)
    return -1;
  int low = 0, hi = i - 1;
  while (low < hi) {
    int t = (low + hi) / 2 + 1;
    if (rmq.qry(t + 1, i) >= h[i] + d)
      low = t;
    else
      hi = t - 1;
  }
  return low;
}
int Gr(int i, int d) {
  if (rmq.qry(i, n - 2) < h[i] + d)
    return n;
  int low = i + 1, hi = n - 1;
  while (low < hi) {
    int t = (low + hi) / 2;
    if (rmq.qry(i, t - 1) >= h[i] + d)
      hi = t;
    else
      low = t + 1;
  }
  return low;
}

int max_towers(int l, int r, int d) {
  int low = 1, hi = n;
  while (low < hi) {
    int t = (low + hi) / 2 + 1;
    if (v[u[t - 1]] >= d)
      low = t;
    else
      hi = t - 1;
  }
  int x = s1::sm(v1[low], 0, n - 1, l, r);
  int L = s1::gr(v1[low], 0, n - 1, l);
  if (L != -1) {
    int l_ = Gl(L, d);
    if (s2::qry(l, l_) >= d || (l <= l_ && rmq.qry(max(l, l_), L) - s2::val(l, l_) >= d)) {
      x++;
      debug(L, l_);
    }
  }
  int R = s1::gl(v1[low], 0, n - 1, r);
  if (R != -1) {
    int r_ = Gr(R, d);
    if (s3::qry(r_, r) >= d || (r_ <= r && rmq.qry(R, min(r, r_)) - s3::val(r_, r) >= d)) {
      x++;
      debug(R, r_);
    }
  }
  return max(1, x);
}

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:7:22: warning: statement has no effect [-Wunused-value]
    7 |   #define debug(...) 0
      |                      ^
towers.cpp:292:7: note: in expansion of macro 'debug'
  292 |       debug(L, l_);
      |       ^~~~~
towers.cpp:7:22: warning: statement has no effect [-Wunused-value]
    7 |   #define debug(...) 0
      |                      ^
towers.cpp:300:7: note: in expansion of macro 'debug'
  300 |       debug(R, r_);
      |       ^~~~~

• 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