oj.uz

Submission #877743

# Submission time Handle Problem Language Result Execution time Memory
877743 2023-11-23T13:46:45 Z Kanon Comparing Plants (IOI20_plants) C++14
30 / 100
 1668 ms 140392 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);

  }

  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];

      u = (1LL * v + sR[i - 1][v]) % n;
      sR[i][v] = sR[i - 1][v] + sR[i - 1][u];

    }
  }

}


int goR(long long 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(long long 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 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 3040 KB Output is correct
7 Correct 257 ms 11632 KB Output is correct
8 Correct 1257 ms 91836 KB Output is correct
9 Correct 1192 ms 92064 KB Output is correct
10 Correct 1178 ms 92060 KB Output is correct
11 Correct 1194 ms 90300 KB Output is correct
12 Correct 1179 ms 90432 KB Output is correct
13 Correct 1327 ms 90680 KB Output is correct
14 Correct 1290 ms 90424 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 8 ms 856 KB Output is correct
7 Correct 236 ms 4948 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 8 ms 936 KB Output is correct
10 Correct 238 ms 4888 KB Output is correct
11 Correct 209 ms 5012 KB Output is correct
12 Correct 204 ms 5012 KB Output is correct
13 Correct 240 ms 4988 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 8 ms 856 KB Output is correct
7 Correct 236 ms 4948 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 8 ms 936 KB Output is correct
10 Correct 238 ms 4888 KB Output is correct
11 Correct 209 ms 5012 KB Output is correct
12 Correct 204 ms 5012 KB Output is correct
13 Correct 240 ms 4988 KB Output is correct
14 Correct 340 ms 11632 KB Output is correct
15 Runtime error 1303 ms 140324 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 179 ms 4080 KB Output is correct
4 Correct 1196 ms 90676 KB Output is correct
5 Correct 1263 ms 91832 KB Output is correct
6 Correct 1358 ms 92096 KB Output is correct
7 Correct 1668 ms 90500 KB Output is correct
8 Runtime error 1248 ms 140392 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 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 1 ms 348 KB Output is correct
6 Correct 4 ms 532 KB Output is correct
7 Correct 37 ms 1108 KB Output is correct
8 Correct 38 ms 1084 KB Output is correct
9 Correct 36 ms 1092 KB Output is correct
10 Correct 38 ms 1188 KB Output is correct
11 Correct 37 ms 1100 KB Output is correct
12 Correct 36 ms 1108 KB Output is correct
13 Correct 39 ms 1108 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 5 ms 860 KB Output is correct
6 Correct 1070 ms 92016 KB Output is correct
7 Correct 1254 ms 92088 KB Output is correct
8 Correct 1343 ms 90500 KB Output is correct
9 Runtime error 1330 ms 140124 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 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 3040 KB Output is correct
7 Correct 257 ms 11632 KB Output is correct
8 Correct 1257 ms 91836 KB Output is correct
9 Correct 1192 ms 92064 KB Output is correct
10 Correct 1178 ms 92060 KB Output is correct
11 Correct 1194 ms 90300 KB Output is correct
12 Correct 1179 ms 90432 KB Output is correct
13 Correct 1327 ms 90680 KB Output is correct
14 Correct 1290 ms 90424 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 344 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 856 KB Output is correct
21 Correct 236 ms 4948 KB Output is correct
22 Correct 5 ms 344 KB Output is correct
23 Correct 8 ms 936 KB Output is correct
24 Correct 238 ms 4888 KB Output is correct
25 Correct 209 ms 5012 KB Output is correct
26 Correct 204 ms 5012 KB Output is correct
27 Correct 240 ms 4988 KB Output is correct
28 Correct 340 ms 11632 KB Output is correct
29 Runtime error 1303 ms 140324 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -