oj.uz

Submission #877729

# Submission time Handle Problem Language Result Execution time Memory
877729 2023-11-23T13:27:57 Z Kanon Comparing Plants (IOI20_plants) C++14
30 / 100
 1710 ms 143928 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) {
  int 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) {
  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];
    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 1 ms 348 KB Output is correct
2 Correct 0 ms 344 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 96 ms 4176 KB Output is correct
7 Correct 229 ms 13748 KB Output is correct
8 Correct 1182 ms 95000 KB Output is correct
9 Correct 1107 ms 94976 KB Output is correct
10 Correct 1232 ms 94840 KB Output is correct
11 Correct 1218 ms 93416 KB Output is correct
12 Correct 1164 ms 93216 KB Output is correct
13 Correct 1315 ms 93200 KB Output is correct
14 Correct 1240 ms 93660 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 432 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 180 ms 6732 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 7 ms 976 KB Output is correct
10 Correct 183 ms 6780 KB Output is correct
11 Correct 154 ms 6748 KB Output is correct
12 Correct 164 ms 6780 KB Output is correct
13 Correct 180 ms 6780 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 432 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 180 ms 6732 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 7 ms 976 KB Output is correct
10 Correct 183 ms 6780 KB Output is correct
11 Correct 154 ms 6748 KB Output is correct
12 Correct 164 ms 6780 KB Output is correct
13 Correct 180 ms 6780 KB Output is correct
14 Correct 285 ms 13748 KB Output is correct
15 Runtime error 1326 ms 143928 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 428 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 134 ms 5656 KB Output is correct
4 Correct 1168 ms 93236 KB Output is correct
5 Correct 1175 ms 95436 KB Output is correct
6 Correct 1432 ms 95104 KB Output is correct
7 Correct 1710 ms 93764 KB Output is correct
8 Runtime error 1319 ms 143768 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 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 3 ms 348 KB Output is correct
7 Correct 26 ms 1424 KB Output is correct
8 Correct 28 ms 1372 KB Output is correct
9 Correct 26 ms 1368 KB Output is correct
10 Correct 26 ms 1420 KB Output is correct
11 Correct 24 ms 1368 KB Output is correct
12 Correct 24 ms 1368 KB Output is correct
13 Correct 27 ms 1420 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 1 ms 440 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 1063 ms 94284 KB Output is correct
7 Correct 1198 ms 94728 KB Output is correct
8 Correct 1390 ms 93108 KB Output is correct
9 Runtime error 1396 ms 142896 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 1 ms 348 KB Output is correct
2 Correct 0 ms 344 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 96 ms 4176 KB Output is correct
7 Correct 229 ms 13748 KB Output is correct
8 Correct 1182 ms 95000 KB Output is correct
9 Correct 1107 ms 94976 KB Output is correct
10 Correct 1232 ms 94840 KB Output is correct
11 Correct 1218 ms 93416 KB Output is correct
12 Correct 1164 ms 93216 KB Output is correct
13 Correct 1315 ms 93200 KB Output is correct
14 Correct 1240 ms 93660 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 432 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 180 ms 6732 KB Output is correct
22 Correct 4 ms 348 KB Output is correct
23 Correct 7 ms 976 KB Output is correct
24 Correct 183 ms 6780 KB Output is correct
25 Correct 154 ms 6748 KB Output is correct
26 Correct 164 ms 6780 KB Output is correct
27 Correct 180 ms 6780 KB Output is correct
28 Correct 285 ms 13748 KB Output is correct
29 Runtime error 1326 ms 143928 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -