oj.uz

Submission #877601

# Submission time Handle Problem Language Result Execution time Memory
877601 2023-11-23T10:58:48 Z Kanon Comparing Plants (IOI20_plants) C++14
30 / 100
 1550 ms 79348 KB 
#include <bits/stdc++.h>
#include "plants.h"
 
using namespace std;
 
class segtree {
  public:
  struct node {
    // info here
    int min_val = 0;
    int min_pos = -1;
    int ad = 0;
 
    void apply(int l, int r, int v) {
      // add parameter above
      ad += v;
      min_val += v;
      if (min_pos == -1) min_pos = l;
    }
    // segtree beat here
  };
 
  node unite(const node &a, const node &b) const {
    node res;
    res.min_val = min(a.min_val, b.min_val);
    if (res.min_val != a.min_val) res.min_pos = b.min_pos;
    else if (res.min_val != b.min_val) res.min_pos = a.min_pos;
    else res.min_pos = min(a.min_pos, b.min_pos);
    // unite here
    return res;
  }
 
  inline void push(int x, int l, int r) {
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    // lazy here
    if (tree[x].ad != 0) {
      tree[x + 1].apply(l, y, tree[x].ad);
      tree[z].apply(y + 1, r, tree[x].ad);
    }
  }
 
  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }
 
  int n;
  vector<node> tree;
 
  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }
 
  template <typename M, typename... T>
  void build(int x, int l, int r, const vector<M> &v, const T&... t) {
    if (l == r) {
      tree[x].apply(l, r, v[l], t...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v, t...);
    build(z, y + 1, r, v, t...);
    pull(x, z);
  }
 
  template <typename M, typename... T>
  segtree(const vector<M> &v, const T&... t) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v, t...);
  }
 
  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }
 
  segtree(){};
 
  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }
 
  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }
 
  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }
 
  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    // segtree beat condition here
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    // A:;
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }
 
  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }
 
  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once
 
  int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }
 
  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
 
  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }
 
  int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }
 
  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
 
  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
 
};
/* HOW TO USE
  node                                    (Modify here)
    info
    apply(int l, int r, ...)
    // segtree beat condition f
 
  unite(node, node)                       (Modify here)
  push(x, l, r)                           (Modify here)
  pull(x, z)
 
  n, vector<node> tree
 
  build(x, l, r)
  segtree(n)
 
  build(x, l, r, vector, state_parameter...)
  segtree(vector, state_parameter...)
 
  get(x, l, r, ll, rr) => get(ll, rr) + get(p)
  modify(x, l, r, ll, rr, ...) => modify(ll, rr, ...)
    // if (f) goto A                                      (Modify here)
    if (l <= ll && rr <= r)
    //A:;                                                 (Modify here)
 
  find_first_knowingly(x, l, r, &f) (not bounded by ll, rr) => find_first(x, l, r, ll, rr, &f) => find_first(ll, rr, &f)
  find_last_knowingly(x, l, r, &f) (not bounded by ll, rr) => find_last(x, l, r, ll, rr, &f) => find_last(ll, rr, &f)
*/
 
const int inf = 1e9;
const int N = 20;
 
int n;
vector<int> position;
vector<vector<int>> sL;
vector<vector<int>> sR;
vector<int> order;
int step;
 
void init(int k, vector<int> a) {
 
  position.clear();
  sL.clear();
  sR.clear();
  order.clear();
 
  n = a.size();
  step = k;
 
  vector<int> A(2 * n);
  for (int i = 0; i < 2 * n; i++) A[i] = a[i % n];
  segtree st(A);
 
  position.resize(n);
  sL.resize(N, vector<int>(n));
  sR.resize(N, vector<int>(n));
 
  set<int> roots;
 
  auto check = [&](int pos) {
    return st.get(pos + n - (k - 1), pos + n - 1).min_val > 0;
  };
 
  auto erase = [&](int pos) {
 
    roots.erase(pos);
 
    st.modify(pos + n - (k - 1), pos + n - 1, -1);
    if (pos > 0) st.modify(max(0, pos - (k - 1)), pos - 1, -1);
    if (pos - (k - 1) < 0) st.modify(pos - (k - 1) + 2 * n, 2 * n - 1, -1);
    st.modify(pos, pos, inf);
    st.modify(pos + n, pos + n, inf);
 
    auto Lnd = st.get(pos + n - (k - 1), pos + n - 1);
    if (Lnd.min_val == 0) {
      int p = Lnd.min_pos;
      if (p >= n) p -= n;
      if (check(p)) {
        roots.insert(p);
      }
    }
 
    auto Rnd = st.get(pos + 1, pos + k - 1);
    if (Rnd.min_val == 0) {
      int p = Rnd.min_pos;
      if (p >= n) p -= n;
      if (check(p)) {
        roots.insert(p);
      }
    }
 
  };
 
  for (int i = 0; i < n; i++) if (a[i] == 0 && check(i)) roots.insert(i);
  while (roots.size()) {
    auto it = roots.begin();
    order.push_back(*it);
    erase(*it);
  }
  assert((int) order.size() == n);
 
  for (int i = 0; i < n; i++) position[order[i]] = i;
  segtree segs(vector<int>(2 * n, inf));
 
 
  reverse(order.begin(), order.end());
  for (int v : order) {
 
    sL[0][v] = 0;
    sR[0][v] = 0;
 
    auto Lnd = segs.get(v + n - (k - 1), v + n);
    auto Rnd = segs.get(v, v + (k - 1));
 
    if (Lnd.min_val < inf) {
      int p = Lnd.min_pos;
      sL[0][v] += v + n - p;
    }
 
    if (Rnd.min_val < inf) {
      int p = Rnd.min_pos;
      sR[0][v] += p - v;
    }
 
    segs.modify(v, v, position[v] - inf);
    segs.modify(v + n, v + n, position[v] - inf);
 
  }
 
  for (int i = 1; i < N; i++) {
    for (int v = 0; v < n; v++) {
 
      int u;
 
      u = v - sL[i - 1][v];
      u %= n;
      if (u < 0) u += n;
      sL[i][v] = sL[i - 1][v] + sL[i - 1][u];
 
      u = v + sR[i - 1][v];
      u %= n;
      sR[i][v] = sR[i - 1][v] + sR[i - 1][u];
 
    }
  }
 
}
 
 
int goR(int x, int y) {
  int len = y - x + (step - 1);
  int goal = position[y % n];
  for (int b = N - 1; b >= 0; b--) {
    int d = sR[b][x % n];
    if (position[(x + d) % n] <= goal) {
      len -= d;
      x += d;
    }
  }
  if (len > 2 * (step - 1)) return -1;
  return x % n;
}
 
int goL(int x, int y) {
  int len = x - y + (step - 1);
  int goal = position[(y + n) % n];
  for (int b = N - 1; b >= 0; b--) {
    int d = sL[b][((x % n) + n) % n];
    if (position[(((x - d) % n) + n) % n] <= goal) {
      len -= d;
      x -= d;
    }
  }
  if (len > 2 * (step - 1)) return -1;
  return ((x % n) + n) % n;
}
 
int compare_plants(int x, int y) {
 
  int ret;
  if (position[x] < position[y]) ret = 1;
  else ret = -1;
 
  if (position[x] > position[y]) swap(x, y);
 
  bool path = false;
 
  int v;
 
  v = goR(x, x < y ? y : y + n);
  if (v != -1 && position[v] <= position[y]) path = true;
  v = goL(x, x > y ? y : y - n);
  if (v != -1 && position[v] <= position[y]) path = true;
 
  if (!path) ret = 0;
 
  return ret;
 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 150 ms 4032 KB Output is correct
7 Correct 253 ms 10608 KB Output is correct
8 Correct 1071 ms 63096 KB Output is correct
9 Correct 1014 ms 63040 KB Output is correct
10 Correct 1027 ms 63116 KB Output is correct
11 Correct 1000 ms 62940 KB Output is correct
12 Correct 978 ms 63044 KB Output is correct
13 Correct 1140 ms 62932 KB Output is correct
14 Correct 1088 ms 62988 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 8 ms 796 KB Output is correct
7 Correct 235 ms 5948 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 8 ms 820 KB Output is correct
10 Correct 230 ms 6012 KB Output is correct
11 Correct 200 ms 6000 KB Output is correct
12 Correct 195 ms 6068 KB Output is correct
13 Correct 234 ms 6040 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 8 ms 796 KB Output is correct
7 Correct 235 ms 5948 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 8 ms 820 KB Output is correct
10 Correct 230 ms 6012 KB Output is correct
11 Correct 200 ms 6000 KB Output is correct
12 Correct 195 ms 6068 KB Output is correct
13 Correct 234 ms 6040 KB Output is correct
14 Correct 335 ms 10540 KB Output is correct
15 Runtime error 1303 ms 79348 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 169 ms 5124 KB Output is correct
4 Correct 1048 ms 62924 KB Output is correct
5 Correct 1113 ms 63468 KB Output is correct
6 Correct 1304 ms 63304 KB Output is correct
7 Correct 1550 ms 63552 KB Output is correct
8 Runtime error 1212 ms 79336 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 35 ms 1292 KB Output is correct
8 Correct 37 ms 1372 KB Output is correct
9 Correct 36 ms 1372 KB Output is correct
10 Correct 38 ms 1368 KB Output is correct
11 Correct 35 ms 1368 KB Output is correct
12 Correct 36 ms 1340 KB Output is correct
13 Correct 39 ms 1372 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 544 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 1040 ms 62328 KB Output is correct
7 Correct 1170 ms 62784 KB Output is correct
8 Correct 1331 ms 62580 KB Output is correct
9 Runtime error 1247 ms 78668 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 150 ms 4032 KB Output is correct
7 Correct 253 ms 10608 KB Output is correct
8 Correct 1071 ms 63096 KB Output is correct
9 Correct 1014 ms 63040 KB Output is correct
10 Correct 1027 ms 63116 KB Output is correct
11 Correct 1000 ms 62940 KB Output is correct
12 Correct 978 ms 63044 KB Output is correct
13 Correct 1140 ms 62932 KB Output is correct
14 Correct 1088 ms 62988 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 8 ms 796 KB Output is correct
21 Correct 235 ms 5948 KB Output is correct
22 Correct 5 ms 348 KB Output is correct
23 Correct 8 ms 820 KB Output is correct
24 Correct 230 ms 6012 KB Output is correct
25 Correct 200 ms 6000 KB Output is correct
26 Correct 195 ms 6068 KB Output is correct
27 Correct 234 ms 6040 KB Output is correct
28 Correct 335 ms 10540 KB Output is correct
29 Runtime error 1303 ms 79348 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -