oj.uz

Submission #1057758

# Submission time Handle Problem Language Result Execution time Memory
1057758 2024-08-14T05:35:54 Z erray Radio Towers (IOI22_towers) C++17
17 / 100
 769 ms 125368 KB 
#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_id, last_id;
    int ct;
    info() { } 
    void init() {
      first_id = -1, last_id = -1;
      ct = 0;
    }
  };
  info I() {
    static info res;
    res.init();
    return res;
  }
  info unite(info l, info r) {
    info res;
    res.first_id = (l.first_id == -1 ? r.first_id : l.first_id);
    res.last_id = (r.last_id == -1 ? l.last_id : r.last_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 new_v = new_node();
    if (v != -1) {
      tree[new_v].dupe(tree[v]);
    } else {
      tree[new_v].init();
    }
    v = new_v;
    if (l == r) {
      tree[v].i.last_id = tree[v].i.first_id = x;
      tree[v].i.ct = (x != -1);
      return v;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) {
      tree[v].L = modify(tree[v].L, l, mid, p, x);
    } else {
      tree[v].R = modify(tree[v].R, mid + 1, r, p, x);
    }
    pull(v);
    //debug("pull", v, l, r, tree[v].i.ct, tree[v].i.first_id, tree[v].i.last_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_id, tree[v].i.last_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(int tree_id, int p, int v) {
    return modify(tree_id, 0, max_N, p, v);
  }
  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_id, i.last_id, i.ct};
  }
};
 
int N, LG, root;
vector<int> H, L, R, tour, tin, tout;
SparseTable<int> min_H, max_H, lca_st;
int get_lca(int v, int u) {
  if (tin[v] > tin[u]) {
    swap(v, u);
  }
  if (tout[v] >= tout[u]) {
    return v;
  }
  return lca_st.get(tout[v], tin[u]);
}
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) {
  debug("hello?");
  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), tin.resize(N), tout.resize(N);
  vector<int> par(N, -1);
  vector<int> mn(N); iota(mn.begin(), mn.end(), 0);
  auto Dfs = [&](int l, int r, auto&& Dfs) -> int {
    int v = max_H.get(l, r);
    tin[v] = int(tour.size());
    tour.push_back(v);
    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]) {
      if (H[mn[u]] < H[mn[v]]) mn[v] = mn[u];
      mn[v] = min(mn[v], mn[u]);
      par[u] = v;
      tour.push_back(v);
    }
    tout[v] = int(tour.size()) - 1;
    return v;
  };
  root = Dfs(0, N - 1, Dfs);
  debug(L, R);
  lca_st = SparseTable<int>(tour, [&](int x, int y) {
    return H[x] > H[y] ? x : y;
  });
  vector<int> act_t(N), dis_t(N);
  for (int i = 0; i < N; ++i) {
    act_t[i] = H[i] - H[mn[i]] + 1;
  }
  for (int i = 0; i < N; ++i) {
    int p = par[i];
    dis_t[i] = (p == -1 ? max_D : H[p] - H[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);
  }
  for (int i = 0; i < N; ++i) {
    updates[get_time(act_t[i])].push_back(i);
  }
  int segtree = PST::new_node();
  for (int i = 0; i < S; ++i) {
    debug(i, times[i]);
    for (auto x : updates[i]) {
      int val, ind;
      if (x < 0) {
        ind = mn[~x];
        val = -1;
      } else {
        ind = mn[x];
        val = mn[x];
      }
      segtree = PST::modify(segtree, ind, val);
    }
    //debug(i, segtree);
    segtrees.push_back(segtree);
  }
}
 
int max_towers(int QL, int QR, int D) {
  int t = get_time(D);
  auto[l, r, ct] = PST::get_ids(segtrees[t], QL, QR);
  int prev_id = (QL > 0 ? PST::get_ids(segtrees[t], 0, QL - 1)[1] : -1);
  int next_id = (QR < N - 1 ? PST::get_ids(segtrees[t], QR + 1, N - 1)[0] : -1);
  debug(l, r, prev_id, next_id);
  if (l == -1) {
    if (prev_id == -1 || next_id == -1) {
      return 1;
    }
    int lca = get_lca(prev_id, next_id);
    assert(l <= lca && r <= lca);
    if (QL < lca && lca < QR && H[lca] - max(H[min_H.get(QL, lca)], H[min_H.get(lca, QR)]) >= D) {
      return 2;
    } else {
      return 1;
    }
  } else {
    if (prev_id != -1) {
      int lca = get_lca(prev_id, l);
      debug(lca);
      if (QL < lca && H[lca] - max(H[l], H[min_H.get(QL, lca)]) >= D) {
        ct++; 
      }
    }
    if (next_id != -1) {
      int lca = get_lca(r, next_id);
      if (lca < QR && H[lca] - max(H[min_H.get(lca, QR)], H[r]) >= D) {
        ct++;
      }
    }
    return ct;
  }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 317 ms 73280 KB 24863rd lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB 1st lines differ - on the 1st token, expected: '13', found: '15'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB 1st lines differ - on the 1st token, expected: '13', found: '15'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 636 ms 112576 KB 1st lines differ - on the 1st token, expected: '11903', found: '11902'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 26268 KB Output is correct
2 Correct 769 ms 112820 KB Output is correct
3 Correct 709 ms 112808 KB Output is correct
4 Correct 680 ms 112564 KB Output is correct
5 Correct 747 ms 112564 KB Output is correct
6 Correct 695 ms 112308 KB Output is correct
7 Correct 671 ms 112344 KB Output is correct
8 Correct 640 ms 125268 KB Output is correct
9 Correct 654 ms 125364 KB Output is correct
10 Correct 606 ms 119476 KB Output is correct
11 Correct 632 ms 120244 KB Output is correct
12 Correct 115 ms 113012 KB Output is correct
13 Correct 118 ms 112564 KB Output is correct
14 Correct 112 ms 112512 KB Output is correct
15 Correct 90 ms 125204 KB Output is correct
16 Correct 90 ms 122200 KB Output is correct
17 Correct 125 ms 109444 KB Output is correct
18 Correct 117 ms 112820 KB Output is correct
19 Correct 119 ms 112972 KB Output is correct
20 Correct 111 ms 112376 KB Output is correct
21 Correct 114 ms 112396 KB Output is correct
22 Correct 122 ms 112564 KB Output is correct
23 Correct 115 ms 112564 KB Output is correct
24 Correct 86 ms 125364 KB Output is correct
25 Correct 84 ms 125368 KB Output is correct
26 Correct 88 ms 117428 KB Output is correct
27 Correct 88 ms 124568 KB Output is correct
28 Correct 2 ms 3160 KB Output is correct
29 Correct 2 ms 3160 KB Output is correct
30 Correct 2 ms 3160 KB Output is correct
31 Correct 2 ms 3296 KB Output is correct
32 Correct 2 ms 3416 KB Output is correct
33 Correct 1 ms 2904 KB Output is correct
34 Correct 2 ms 3160 KB Output is correct
35 Correct 2 ms 3160 KB Output is correct
36 Correct 2 ms 3160 KB Output is correct
37 Correct 2 ms 3160 KB Output is correct
38 Correct 2 ms 3160 KB Output is correct
39 Correct 2 ms 3160 KB Output is correct
40 Correct 2 ms 3416 KB Output is correct
41 Correct 2 ms 3416 KB Output is correct
42 Correct 2 ms 3480 KB Output is correct
43 Correct 2 ms 3416 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB 1st lines differ - on the 1st token, expected: '13', found: '15'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 317 ms 73280 KB 24863rd lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -