Submission #1057337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057337		erray	송신탑 (IOI22_towers)	C++17	0 / 100	247 ms	308040 KiB

towers

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

using namespace std;

#ifdef DEBUG 
  #include "/home/hp/contests/debug.h"
#else 
  #define debug(...) void(37)
#endif

constexpr int max_D = int(1e9) + 1;

template<typename T, typename F = function<T(const T&, const T&)>>
struct SparseTable {
  vector<vector<T>> table;
  int n;
  F op;
  SparseTable () {} 
  SparseTable(vector<T> a, F _op) : op(_op) {
    n = int(a.size());
    int lg = __lg(n) + 1;
    table.resize(lg + 1);
    table[0] = a;
    for (int l = 1; l < lg; ++l) {
      int s = n - (1 << l) + 1;
      table[l].resize(s);
      for (int i = 0; i < s; ++i) {
        table[l][i] = op(table[l - 1][i], table[l - 1][i + (1 << (l - 1))]);
      } 
    }
  }
  T get(int l, int r) {
    int lg = __lg(r - l + 1);
    return op(table[lg][l], table[lg][r - (1 << lg) + 1]);
  }
};

constexpr int MAX_NODES = int(2e5) * 20 * 8;
int max_N = int(1e5);
namespace PST {
  int t = 0;
  struct info {
    int first_r_id, last_l_id;
    int ct;
    info() { } 
    void init() {
      first_r_id = -1, last_l_id = -1;
      ct = 0;
    }
  };
  info I() {
    static info res;
    res.init();
    return res;
  }
  info unite(info l, info r) {
    info res;
    res.first_r_id = (l.first_r_id == -1 ? r.first_r_id : l.first_r_id);
    res.last_l_id = (r.last_l_id == -1 ? l.last_l_id : r.last_l_id);
    res.ct = l.ct + r.ct;
    return res;
  }
  
  struct node {
    int L, R;
    info i;
    void init() { 
      L = R = -1;
      i.init();
    }
    void dupe(const node& x) {
      L = x.L, R = x.R;
      i = x.i;
    }
  };
  node tree[MAX_NODES];
  int new_node() {
    tree[t].init();
    t++;
    return t - 1;
  }
  void pull(int v) {
    tree[v].i = unite(tree[v].L == -1 ? I() : tree[tree[v].L].i, tree[v].R == -1 ? I() : tree[tree[v].R].i);
  }
  int modify(int v, int l, int r, int p, int x, int type) {
    int new_v = new_node();
    if (v != -1) {
      tree[new_v].dupe(tree[v]);
    } else {
      tree[new_v].init();
    }
    v = new_v;
    if (l == r) {
      if (type) {
        tree[v].i.first_r_id = x;
      } else {
        tree[v].i.last_l_id = x;
        tree[v].i.ct = (x != -1);
      }
    //debug("update", v, l, r, tree[v].i.ct, tree[v].i.first_r_id, tree[v].i.last_l_id);
      
      return v;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) {
      tree[v].L = modify(tree[v].L, l, mid, p, x, type);
    } else {
      tree[v].R = modify(tree[v].R, mid + 1, r, p, x, type);
    }
    pull(v);
    //debug("pull", v, l, r, tree[v].i.ct, tree[v].i.first_r_id, tree[v].i.last_l_id);

    return v;
  }
  info get(int v, int l, int r, int ll, int rr) {
    //debug(v, l, r, tree[v].i.ct, tree[v].i.first_r_id, tree[v].i.last_l_id);
    if (l >= ll && rr >= r) {
      return tree[v].i;
    }
    int mid = (l + r) >> 1;
    info res;
    res.init();
    if (ll <= mid && tree[v].L != -1) {
      res = unite(res, get(tree[v].L, l, mid, ll, rr));
    } 
    if (mid < rr && tree[v].R != -1) {
      res = unite(res, get(tree[v].R, mid + 1, r, ll, rr));
    }
    return res;
  }
  int modify_L(int tree_id, int p, int v) {
    return modify(tree_id, 0, max_N, p, v, 0);
  }
  int modify_R(int tree_id, int p, int v) {
    return modify(tree_id, 0, max_N, p, v, 1);
  }
  array<int, 3> get_ids(int tree_id, int l, int r) {
    auto i = get(tree_id, 0, max_N, l, r);
    return {i.first_r_id, i.last_l_id, i.ct};
  }
};

int N, LG, root;
vector<int> H, L, R;
vector<vector<int>> lift;
SparseTable<int> min_H, max_H;
int S;
vector<int> times, segtrees;
int get_time(int x) {
  assert(times[0] <= x);
  return int(lower_bound(times.begin(), times.end(), x + 1) - times.begin()) - 1;
}

void init(int _N, std::vector<int> _H) {
  N = _N; H = _H;
  LG = __lg(N) + 1;
  vector<int> foo(N); iota(foo.begin(), foo.end(), 0);
  min_H = SparseTable<int>(foo, [&](int x, int y) {
    return (H[x] < H[y] ? x : y);
  });
  max_H = SparseTable<int>(foo, [&](int x, int y) {
    return (H[x] > H[y] ? x : y);
  });
  vector<vector<int>> g(N);
  L.resize(N), R.resize(N);
  lift.resize(LG, vector<int>(N, -1));
  auto mn = H;
  auto Dfs = [&](int l, int r, auto&& Dfs) -> int {
    int v = max_H.get(l, r);
    L[v] = l, R[v] = r;
    if (l != v) {
      g[v].push_back(Dfs(l, v - 1, Dfs));
    }
    if (r != v) {
      g[v].push_back(Dfs(v + 1, r, Dfs));
    }
    for (auto u : g[v]) {
      mn[v] = min(mn[v], mn[u]);
      lift[0][u] = v;
    }
    return v;
  };
  root = Dfs(0, N - 1, Dfs);
  debug(root, L, R, lift);
  for (int l = 1; l < LG; ++l) {
    for (int i = 0; i < N; ++i) {
      int next = lift[l - 1][i];
      if (next == -1) {
        lift[l][i] = -1;
      } else {
        lift[l][i] = lift[l - 1][next];
      }
    }
  }
  vector<int> act_t(N), dis_t(N);
  for (int i = 0; i < N; ++i) {
    act_t[i] = H[i] - mn[i] + 1;
  }
  for (int i = 0; i < N; ++i) {
    int p = lift[0][i];
    dis_t[i] = (p == -1 ? max_D : H[p] - mn[i] + 1); 
  }
  debug(act_t, dis_t);
  // each segment is active in the range [act_t_i, dis_t_i) 
  for (int i = 0; i < N; ++i) {
    times.push_back(act_t[i]);
    times.push_back(dis_t[i]);
  }
  sort(times.begin(), times.end());
  times.erase(unique(times.begin(), times.end()), times.end());
  S = int(times.size());
  vector<vector<int>> updates(S);
  for (int i = 0; i < N; ++i) {
    updates[get_time(dis_t[i])].push_back(~i);
    updates[get_time(act_t[i])].push_back(i);
  }
  int segtree = PST::new_node();
  for (int i = 0; i < S; ++i) {
    for (auto x : updates[i]) {
      int val, ind;
      if (x < 0) {
        ind = ~x;
        val = -1;
      } else {
        ind = x;
        val = x;
      }
      debug(ind, val, L[ind], R[ind]);
      segtree = PST::modify_L(segtree, L[ind], val);
      segtree = PST::modify_R(segtree, R[ind], val);
    }
    //debug(i, segtree);
    segtrees.push_back(segtree);
  }
}

int max_towers(int QL, int QR, int D) {
  int t = get_time(D);
  debug(QL, QR, D, t);
  int st_id = segtrees[t];
  
  int first_r = PST::get_ids(st_id, 0, QL)[1];
  int last_l = PST::get_ids(st_id, QR, max_N)[0];
  //auto[first_r, last_l, foo] = PST::get_ids(st_id, QL, QR);
  debug(first_r, last_l, st_id);
  int ll = (first_r == -1 ? 0 : R[first_r] + 1);
  int rr = (last_l == -1 ? max_N : L[last_l] - 1);
  auto[l_block, r_block, inside] = (ll <= rr ? PST::get_ids(st_id, ll, rr) : array<int, 3>{-1, -1, 0});
  auto Binary_lift = [&](int v, function<bool(int)> good) {
    for (int l = LG - 1; l >= 0; --l) {
      int u = lift[l][v];
      if (u != -1 && !good(u)) {
        v = u;
      }
    }
    return v;
  };
  if (first_r != -1) {
    first_r = Binary_lift(first_r, [&](int x) {
      return H[x] - min_H.get(QL, R[x]) >= D;
    });
  }
  if (last_l != -1) {
    last_l = Binary_lift(last_l, [&](int x) {
      return H[x] - min_H.get(L[x], QR) >= D;
    });
  }
  if (l_block == -1) {
    if (first_r != -1 && last_l != -1 && R[first_r] < L[last_l]) {
      return 2;
    }
    return 1;
  }
  if (first_r != -1 && R[first_r] < L[l_block]) ++inside;
  if (last_l != -1 && L[last_l] > R[r_block]) ++inside;
  return inside;
}

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