Submission #668652

#	Time	Username	Problem	Language	Result	Execution time	Memory
668652		evenvalue	Comparing Plants (IOI20_plants)	C++17	0 / 100	4019 ms	12156 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;

class LazySegTree {
  struct Node {
    int val = kInf;
    int dec = 0;
  };

  const size_t n;
  vector<Node> t;

  static Node unite(const Node l, const Node r) {
    Node ans{};
    ans.val = min(l.val, r.val);
    return ans;
  }

  void push(const int x, const int l, const int r) {
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    for (const int child : {x + 1, y}) {
      t[child].val -= t[x].dec;
      t[child].dec += t[x].dec;
    }
    t[x].dec = 0;
  }

  void build(const int x, const int l, const int r, const vector<int> &a) {
    if (l == r) {
      t[x].val = a[l];
      t[x].dec = 0;
      return;
    }
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    build(x + 1, l, mid, a);
    build(y, mid + 1, r, a);
    t[x] = unite(t[x + 1], t[y]);
  }

  int find_last_zero(const int x, const int l, const int r, const int ql, const int qr) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    int ans = -1;
    if (ql <= mid and t[x + 1].val == 0) {
      ans = max(ans, find_last_zero(x + 1, l, mid, ql, qr));
    }
    if (mid < qr and t[y].val == 0) {
      ans = max(ans, find_last_zero(y, mid + 1, r, ql, qr));
    }
    return ans;
  }

  void range_update(const int x, const int l, const int r, const int ql, const int qr) {
    if (ql <= l and r <= qr) {
      t[x].val--;
      t[x].dec++;
      return;
    }
    push(x, l, r);
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (ql <= mid) {
      range_update(x + 1, l, mid, ql, qr);
    }
    if (mid < qr) {
      range_update(y, mid + 1, r, ql, qr);
    }
    t[x] = unite(t[x + 1], t[y]);
  }

  void point_update(const int x, const int l, const int r, const int p, const int v) {
    if (l == r) {
      t[x].val = v;
      t[x].dec = 0;
      return;
    }
    push(x, l, r);
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (p <= mid) {
      point_update(x + 1, l, mid, p, v);
    } else {
      point_update(y, mid + 1, r, p, v);
    }
    t[x] = unite(t[x + 1], t[y]);
  }

  Node query(const int x, const int l, const int r, const int ql, const int qr) {
    if (ql <= l and r <= qr) {
      return t[x];
    }
    push(x, l, r);
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (qr <= mid) {
      return query(x + 1, l, mid, ql, qr);
    } else if (mid < ql) {
      return query(y, mid + 1, r, ql, qr);
    } else {
      return unite(query(x + 1, l, mid, ql, qr),
                   query(y, mid + 1, r, ql, qr));
    }
  }

public:
  explicit LazySegTree(const vector<int> &a) : n(a.size()), t(2 * n - 1) {
    build(0, 0, (int) n - 1, a);
  }

  int find_last_zero(const int l, const int r) {
    return find_last_zero(0, 0, (int) n - 1, l, r);
  }

  void range_update(const int l, const int r) {
    range_update(0, 0, (int) n - 1, l, r);
  }

  void point_update(const int p, const int v) {
    point_update(0, 0, (int) n - 1, p, v);
  }

  int query(const int l, const int r) {
    return query(0, 0, (int) n - 1, l, r).val;
  }
};

vector<int> find_valid_arrangement(int k, vector<int> r) {
  const int n = (int) r.size();

  r.insert(r.end(), r.begin(), r.end());

  vector<int> h(n, -1);
  int tall = n - 1;

  LazySegTree st(r);

  auto point_update = [&](const int i) {
    st.point_update(i, kInf);
    st.point_update(i - n, kInf);
  };

  auto range_update = [&](const int i) {
    st.range_update(i - k + 1, i);
    const int l = i - k + 1 - n;
    st.range_update(max(0, l), i - n);
    if (l < 0) st.range_update(2 * n + l, 2 * n - 1);
  };

  function<void(int)> find_height = [&](const int i) {
    const int j = st.find_last_zero(i - k + 1, i - 1);
    if (j != -1) find_height(j);
    h[i - n] = tall--;
    point_update(i);
    range_update(i);
  };

  for (int i = st.find_last_zero(n, 2 * n - 1); i != -1; i = st.find_last_zero(n, 2 * n - 1)) {
    find_height(i);
  }

  return h;
}

int n = 0;
vector<vector<int>> g;

void init(int k, vector<int> r) {
  n = (int) r.size();
  const auto h = find_valid_arrangement(k, std::move(r));

  auto dist = [&](const int i, const int j) {
    return min({abs(i - j), i + n - j, j + n - i});
  };

  g.assign(n, vector<int>(0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (h[i] <= h[j] or dist(i, j) >= k) continue;
      g[i].push_back(j);
    }
  }
}

bool can_go(const int s, const int t) {
  vector<bool> visit(n);
  function<void(int)> dfs = [&](const int x) {
    visit[x] = true;
    for (const int y : g[x]) {
      if (visit[y]) continue;
      dfs(y);
    }
  };
  dfs(s);
  return visit[t];
}

int compare_plants(int x, int y) {
  if (can_go(x, y)) return 1;
  if (can_go(y, x)) return -1;
  return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25