oj.uz

Submission #877751

# Submission time Handle Problem Language Result Execution time Memory
877751 2023-11-23T13:59:03 Z Kanon Comparing Plants (IOI20_plants) C++14
30 / 100
 1939 ms 140380 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<long long>> sL;
vector<vector<long long>> 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<long long>(n));
  sR.resize(N, vector<long long>(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) {
  long long len = y - x + (step - 1);
  int goal = position[y % n];
  for (int b = N - 1; b >= 0; b--) {
    int d = sR[b][x];
    if (position[(x + d) % n] <= goal) {
      len -= d;
      x += d;
      x %= n;
    }
  }
  if (len > 2 * (step - 1)) return -1;
  return x;
}
 
int goL(int x, int y) {
  long long len = x - y + (step - 1);
  int goal = position[(y + n) % n];
  for (int b = N - 1; b >= 0; b--) {
    int d = sL[b][x];
    if (position[(((x - d) % n) + n) % n] <= goal) {
      len -= d;
      x -= d;
      x %= n;
      x = (x + n) % n;
    }
  }
  if (len > 2 * (step - 1)) return -1;
  return x;
}
 
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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 98 ms 3052 KB Output is correct
7 Correct 223 ms 11696 KB Output is correct
8 Correct 1236 ms 92064 KB Output is correct
9 Correct 1191 ms 92064 KB Output is correct
10 Correct 1158 ms 91956 KB Output is correct
11 Correct 1151 ms 90500 KB Output is correct
12 Correct 1162 ms 90332 KB Output is correct
13 Correct 1330 ms 90536 KB Output is correct
14 Correct 1303 ms 90320 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 7 ms 860 KB Output is correct
7 Correct 178 ms 4960 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 7 ms 860 KB Output is correct
10 Correct 181 ms 4976 KB Output is correct
11 Correct 154 ms 4944 KB Output is correct
12 Correct 160 ms 5160 KB Output is correct
13 Correct 181 ms 4972 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 7 ms 860 KB Output is correct
7 Correct 178 ms 4960 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 7 ms 860 KB Output is correct
10 Correct 181 ms 4976 KB Output is correct
11 Correct 154 ms 4944 KB Output is correct
12 Correct 160 ms 5160 KB Output is correct
13 Correct 181 ms 4972 KB Output is correct
14 Correct 282 ms 11420 KB Output is correct
15 Runtime error 1341 ms 140380 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 128 ms 3920 KB Output is correct
4 Correct 1178 ms 90296 KB Output is correct
5 Correct 1241 ms 91964 KB Output is correct
6 Correct 1369 ms 92352 KB Output is correct
7 Correct 1939 ms 90500 KB Output is correct
8 Runtime error 1464 ms 140304 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 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 24 ms 1116 KB Output is correct
8 Correct 26 ms 1104 KB Output is correct
9 Correct 25 ms 1104 KB Output is correct
10 Correct 28 ms 1100 KB Output is correct
11 Correct 26 ms 1104 KB Output is correct
12 Correct 24 ms 1104 KB Output is correct
13 Correct 29 ms 1108 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 344 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 1031 ms 92092 KB Output is correct
7 Correct 1175 ms 91836 KB Output is correct
8 Correct 1347 ms 90572 KB Output is correct
9 Runtime error 1323 ms 140372 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 98 ms 3052 KB Output is correct
7 Correct 223 ms 11696 KB Output is correct
8 Correct 1236 ms 92064 KB Output is correct
9 Correct 1191 ms 92064 KB Output is correct
10 Correct 1158 ms 91956 KB Output is correct
11 Correct 1151 ms 90500 KB Output is correct
12 Correct 1162 ms 90332 KB Output is correct
13 Correct 1330 ms 90536 KB Output is correct
14 Correct 1303 ms 90320 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 7 ms 860 KB Output is correct
21 Correct 178 ms 4960 KB Output is correct
22 Correct 3 ms 348 KB Output is correct
23 Correct 7 ms 860 KB Output is correct
24 Correct 181 ms 4976 KB Output is correct
25 Correct 154 ms 4944 KB Output is correct
26 Correct 160 ms 5160 KB Output is correct
27 Correct 181 ms 4972 KB Output is correct
28 Correct 282 ms 11420 KB Output is correct
29 Runtime error 1341 ms 140380 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -