Submission #1234561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234561		rxlfd314	Radio Towers (IOI22_towers)	C++20	60 / 100	4035 ms	11072 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

struct ST {
  int N;
  vt<int> st;
  void init(const int n) {
    N = n;
    st.resize(n << 1);
  }
  void update(int i, const int v) {
    st[i += N] = v;
    while (i >>= 1)
      st[i] = min(st[i<<1], st[i<<1|1]);
  }
  int query(int l, int r) {
    int ret = INT_MAX;
    for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        ret = min(ret, st[l++]);
      if (r & 1)
        ret = min(ret, st[--r]);
    }
    return ret;
  }
} st, st2;

constexpr int mxN = 100005, LOG = 16;
int N, K, D, lift[mxN][LOG+1];
vt<int> H;

int max_towers(int l, int r, int d) {
  if (K < 0) {
    if (d != D) {
      D = d;
      vt<int> L(N), R(N), stk = {-1};
      FOR(i, 0, N-1) {
        while (size(stk) > 1 && H[stk.back()] < H[i])
          stk.pop_back();
        int lo = 0, hi = size(stk) - 1;
        while (lo < hi) {
          const int mid = lo + hi + 1 >> 1;
          if (H[i] + D <= H[stk[mid]])
            lo = mid;
          else
            hi = mid - 1;
        }
        L[i] = stk[lo];
        stk.push_back(i);
      }
      stk = {N};
      ROF(i, N-1, 0) {
        while (size(stk) > 1 && H[i] > H[stk.back()])
          stk.pop_back();
        int lo = 0, hi = size(stk) - 1;
        while (lo < hi) {
          const int mid = lo + hi + 1 >> 1;
          if (H[i] + D <= H[stk[mid]])
            lo = mid;
          else
            hi = mid - 1;
        }
        R[i] = stk[lo];
        stk.push_back(i);
      }
      vt<int> sweep(N, N);
      st.init(N);
      st2.init(N);
      FOR(i, 0, N-1) {
        st.update(i, R[i]);
        st2.update(i, -L[i]);
        if (L[i] >= 0)
          sweep[L[i]] = min(sweep[L[i]], R[i]);
      }
      fill(lift[N], lift[N] + LOG + 1, N);
      ROF(i, N-1, 0) {
        if (i+1 < N)
          sweep[i] = min(sweep[i], sweep[i+1]);
        lift[i][0] = sweep[i];
        FOR(j, 1, LOG)
          lift[i][j] = lift[lift[i][j-1]][j-1];
      }
    }
    int i = st.query(l, r), ret = 1;
    if (i > r)
      return 1;
    ROF(j, LOG, 0)
      if (lift[i][j] <= r) {
        i = lift[i][j];
        ret += 1 << j;
      }
    return ret + (-st2.query(i, r) >= i);
  }
  if (K >= 0) {
    if (l >= K || r <= K)
      return 1;
    return max(1, (H[l] + d <= H[K]) + (H[r] + d <= H[K]));
  }
}

void init(int _N, vt<int> _H) {
  N = _N, H = _H;
  K = max_element(all(H)) - H.begin();
  bool sub1 = true;
  FOR(i, 0, K-1)
    sub1 &= H[i] < H[i+1];
  FOR(i, K, N-2)
    sub1 &= H[i] > H[i+1];
  if (!sub1)
    K = -1;
}

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:111:1: warning: control reaches end of non-void function [-Wreturn-type]
  111 | }
      | ^

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