Submission #631223

#	Time	Username	Problem	Language	Result	Execution time	Memory
631223		abeker	Radio Towers (IOI22_towers)	C++17	100 / 100	2315 ms	229444 KiB

towers

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

const int INF = 2e9;

struct Node {
  int cnt;
  Node *l, *r;
  Node(int cnt, Node* l, Node* r) : cnt(cnt), l(l), r(r) {}
  Node() : cnt(0), l(nullptr), r(nullptr) {}
};

class Persistent {
  int offset;
  vector <Node*> root;
  Node* NIL;
public:
  Node* update(Node* x, int lo, int hi, int pos) {
    if (pos < lo || pos >= hi)
      return x;
    if (hi - lo == 1)
      return new Node(x -> cnt + 1, NIL, NIL);
    int mid = lo + (hi - lo) / 2;
    Node* lft = update(x -> l, lo, mid, pos);
    Node* rig = update(x -> r, mid, hi, pos);
    return new Node(lft -> cnt + rig -> cnt, lft, rig);
  }
  Persistent(vector <int> vals) {
    NIL = new Node();
    NIL -> l = NIL -> r = NIL;
    root.push_back(NIL);
    for (auto &it : vals)
      it = min(it, INF / 2);
    int mx = *max_element(vals.begin(), vals.end());
    for (offset = 1; offset < mx; offset *= 2);
    for (int i = 1; i < vals.size(); i++)
      root.push_back(update(root.back(), 0, offset, vals[i]));
  }
  Persistent() {}
  int query(Node* x, int lo, int hi, int from, int to) const {
    if (lo >= to || hi <= from)
      return 0;
    if (lo >= from && hi <= to)
      return x -> cnt;
    int mid = lo + (hi - lo) / 2;
    return query(x -> l, lo, mid, from, to) + query(x -> r, mid, hi, from, to);
  }
  int query(Node* x, int to) const {
    return query(x, 0, offset, 0, to);
  }
  int get(int from, int to, int val) const {
    return query(root[to - 1], val) - query(root[from - 1], val);
  }
};

int N, lg;
vector <int> H;
vector <int> ex;
vector <int> lb, ub;
vector <vector <int>> mini;
vector <vector <int>> lft, rig;
Persistent 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 = Persistent(lb);
  count_ub = Persistent(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.get(l, r + 1, d);
  int smaller_ub = count_ub.get(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 'Persistent::Persistent(std::vector<int>)':
towers.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 1; i < vals.size(); i++)
      |                     ~~^~~~~~~~~~~~~
towers.cpp: In function 'void init_sparse()':
towers.cpp:78:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   78 |       mini[i][j] = min(mini[i][j - 1], i + (1 << j - 1) > N ? INF : mini[i + (1 << j - 1)][j - 1]);
      |                                                  ~~^~~
towers.cpp:78:86: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   78 |       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