oj.uz

Submission #877756

# Submission time Handle Problem Language Result Execution time Memory
877756 2023-11-23T14:06:39 Z Kanon Comparing Plants (IOI20_plants) C++14
25 / 100
 1387 ms 91956 KB 
#include <bits/stdc++.h>
#include "plants.h"
 
using namespace std;
 
template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);
 
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);
 
  }
  debug("foo")
 
  for (int i = 1; i < N; i++) {
    for (int v = 0; v < n; v++) {
 
      int u;
 
      u = (1LL * v - sL[i - 1][v]) % n;
      if (u < 0) u += n;
      sL[i][v] = sL[i - 1][v] + sL[i - 1][u];
      assert(sL[i][v] >= 0);
 
      u = (1LL * v + sR[i - 1][v]) % n;
      sR[i][v] = sR[i - 1][v] + sR[i - 1][u];
      assert(sR[i][v] >= 0);
 
    }
  }
  debug("foo")
 
}
 
 
int goR(long long x, int y) {
  if (n > 100000) return -1;
  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 % n];
    if (position[(x + d) % n] <= goal) {
      len -= d;
      x += d;
    }
  }
  if (len > 2 * (step - 1)) return -1;
  return x % n;
}
 
int goL(long long x, int y) {
  if (n > 100000) return -1;
  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
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 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 149 ms 3048 KB Output is correct
7 Correct 292 ms 11664 KB Output is correct
8 Incorrect 567 ms 91956 KB Output isn't correct
9 Halted 0 ms 0 KB -

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 1 ms 500 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 11 ms 860 KB Output is correct
7 Correct 244 ms 4856 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 11 ms 856 KB Output is correct
10 Correct 264 ms 4968 KB Output is correct
11 Correct 232 ms 4976 KB Output is correct
12 Correct 208 ms 5016 KB Output is correct
13 Correct 248 ms 4816 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 1 ms 500 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 11 ms 860 KB Output is correct
7 Correct 244 ms 4856 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 11 ms 856 KB Output is correct
10 Correct 264 ms 4968 KB Output is correct
11 Correct 232 ms 4976 KB Output is correct
12 Correct 208 ms 5016 KB Output is correct
13 Correct 248 ms 4816 KB Output is correct
14 Correct 378 ms 11636 KB Output is correct
15 Incorrect 1387 ms 90496 KB Output isn't correct
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 196 ms 3932 KB Output is correct
4 Incorrect 662 ms 90492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.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 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 1108 KB Output is correct
8 Correct 39 ms 980 KB Output is correct
9 Correct 36 ms 1100 KB Output is correct
10 Correct 38 ms 1112 KB Output is correct
11 Correct 37 ms 1108 KB Output is correct
12 Correct 35 ms 1108 KB Output is correct
13 Correct 39 ms 1112 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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Incorrect 828 ms 91860 KB Output isn't correct
7 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 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 149 ms 3048 KB Output is correct
7 Correct 292 ms 11664 KB Output is correct
8 Incorrect 567 ms 91956 KB Output isn't correct
9 Halted 0 ms 0 KB -