Submission #631078

#	Time	Username	Problem	Language	Result	Execution time	Memory
631078		abeker	Radio Towers (IOI22_towers)	C++17	100 / 100	2583 ms	69480 KiB

towers

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

const int INF = INT_MAX;

class Orthogonal {
  int offset;
  vector <vector <int>> tour;
public:
  Orthogonal(vector <int> vals) {
    for (offset = 1; offset < vals.size(); offset *= 2);
    tour.resize(2 * offset);
    for (int i = 1; i < vals.size(); i++)
      tour[i + offset].push_back(vals[i]);
    for (int i = offset - 1; i; i--) {
      tour[i].resize(tour[2 * i].size() + tour[2 * i + 1].size());
      merge(tour[2 * i].begin(), tour[2 * i].end(), tour[2 * i + 1].begin(), tour[2 * i + 1].end(), tour[i].begin());
    }
  }
  Orthogonal() {}
  int query(int x, int lo, int hi, int from, int to, int val) {
    if (lo >= to || hi <= from)
      return 0;
    if (lo >= from && hi <= to)
      return lower_bound(tour[x].begin(), tour[x].end(), val) - tour[x].begin();
    int mid = (lo + hi) / 2;
    return query(2 * x, lo, mid, from, to, val) + query(2 * x + 1, mid, hi, from, to, val);
  }
  int query(int from, int to, int val) {
    return query(1, 0, offset, from, to, val);
  }
};

int N, lg;
vector <int> H;
vector <int> ex;
vector <int> lb, ub;
vector <vector <int>> mini;
vector <vector <int>> lft, rig;
Orthogonal count_lb, count_ub;

int query(int from, int to) {
  if (from >= to)
    return INF;
  int tmp = ex[to - from];
  return min(mini[from][tmp], mini[to - (1 << tmp)][tmp]);
}

void init_sparse() {
  mini.resize(N + 1, vector <int> (lg + 1));
  for (int i = 1; i <= N; i++)
    mini[i][0] = H[i];
  for (int j = 1; j <= lg; j++)
    for (int i = 1; i <= N; i++)
      mini[i][j] = min(mini[i][j - 1], i + (1 << j - 1) > N ? INF : mini[i + (1 << j - 1)][j - 1]);
  ex.resize(N + 1);
  for (int i = 2; i <= N; i++)
    ex[i] = ex[i / 2] + 1;
}

void init_lft_rig() {
  lft.resize(N + 2, vector <int> (lg + 1));
  rig.resize(N + 2, vector <int> (lg + 1));
  stack <int> s;
  s.push(0);
  for (int i = 1; i <= N; i++) {
    while (H[s.top()] < H[i])
      s.pop();
    lft[i][0] = s.top();
    s.push(i);
  }
  s = stack <int> ();
  s.push(N + 1);
  for (int i = N; i; i--) {
    while (H[s.top()] < H[i])
      s.pop();
    rig[i][0] = s.top();
    s.push(i);
  }
  rig[N + 1] = vector <int> (lg + 1, N + 1);
  for (int j = 1; j <= lg; j++)
    for (int i = 1; i <= N; i++) {
      lft[i][j] = lft[lft[i][j - 1]][j - 1];
      rig[i][j] = rig[rig[i][j - 1]][j - 1];
    }
}

void init_lb_ub() {
  lb.resize(N + 1);
  ub.resize(N + 1);
  for (int i = 1; i <= N; i++) {
    int tmp = query(lft[i][0] + 1, rig[i][0]);
    lb[i] = H[i] - tmp;
    ub[i] = min(H[lft[i][0]], H[rig[i][0]]) - tmp;
  }
  count_lb = Orthogonal(lb);
  count_ub = Orthogonal(ub);
}

void init(int n, vector <int> h) {
  N = n;
  H.resize(N + 2);
  H[0] = H[N + 1] = INF;
  for (int i = 1; i <= N; i++)
    H[i] = h[i - 1];
  while (1 << lg < N)
    lg++;
  init_sparse();
  init_lft_rig();
  init_lb_ub();
}

int max_towers(int l, int r, int d) {
  l += 1;
  r += 1;
  int smaller_lb = count_lb.query(l, r + 1, d);
  int smaller_ub = count_ub.query(l, r + 1, d);
  auto binary = [&](int x, const function <bool(int)> &check, const vector <vector <int>> &anc) -> pair <int, int> {
    if (!check(x))
      return {0, x};
    int res = 0;
    for (int i = lg; i >= 0; i--)
      if (check(anc[x][i])) {
        x = anc[x][i];
        res |= 1 << i;
      }
    return {res + 1, anc[x][0]};
  };
  auto lb_lft_plus = [&](int node) {
    return rig[node][0] <= r && H[node] - query(l, rig[node][0]) < d;
  };
  auto lb_rig_plus = [&](int node) {
    return lft[node][0] >= l && H[node] - query(lft[node][0] + 1, r + 1) < d;
  };
  auto lb_lft_minus = [&](int node) {
    return rig[node][0] <= r && lb[node] < d;
  };
  auto lb_rig_minus = [&](int node) {
    return lft[node][0] >= l && lb[node] < d;
  };
  auto ub_lft_plus = [&](int node) {
    return rig[node][0] <= r && H[rig[node][0]] - query(l, rig[node][0]) < d;
  };
  auto ub_rig_plus = [&](int node) {
    return lft[node][0] >= l && H[lft[node][0]] - query(lft[node][0] + 1, r + 1) < d;
  };
  auto ub_lft_minus = [&](int node) {
    return rig[node][0] <= r && ub[node] < d;
  };
  auto ub_rig_minus = [&](int node) {
    return lft[node][0] >= l && ub[node] < d;
  };
  auto check_mx = [&](int node) {
    return rig[node][0] <= r;
  };
  smaller_lb += binary(l, lb_lft_plus, rig).first + binary(r, lb_rig_plus, lft).first - binary(l, lb_lft_minus, rig).first - binary(r, lb_rig_minus, lft).first;
  smaller_ub += binary(l, ub_lft_plus, rig).first + binary(r, ub_rig_plus, lft).first - binary(l, ub_lft_minus, rig).first - binary(r, ub_rig_minus, lft).first;
  int arg_max = binary(l, check_mx, rig).second;
  smaller_lb -= lb[arg_max] < d;
  smaller_lb += H[arg_max] - query(l, r + 1) < d;
  smaller_ub -= ub[arg_max] < d;
  return smaller_lb - smaller_ub;
}

Compilation message (stderr)

towers.cpp: In constructor 'Orthogonal::Orthogonal(std::vector<int>)':
towers.cpp:12:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (offset = 1; offset < vals.size(); offset *= 2);
      |                      ~~~~~~~^~~~~~~~~~~~~
towers.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 1; i < vals.size(); i++)
      |                     ~~^~~~~~~~~~~~~
towers.cpp: In function 'void init_sparse()':
towers.cpp:56:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |       mini[i][j] = min(mini[i][j - 1], i + (1 << j - 1) > N ? INF : mini[i + (1 << j - 1)][j - 1]);
      |                                                  ~~^~~
towers.cpp:56:86: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |       mini[i][j] = min(mini[i][j - 1], i + (1 << j - 1) > N ? INF : mini[i + (1 << j - 1)][j - 1]);
      |                                                                                    ~~^~~

• 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