oj.uz

Submission #668674

# Submission time Handle Problem Language Result Execution time Memory
668674 2022-12-04T12:02:21 Z evenvalue Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 65488 KB 
#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);
    ans.dec = 0;
    return ans;
  }

  void push(const int x, const int l, const int r) {
    assert(0 <= x and x < t.size());
    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(const 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) {
    assert(n <= i and i < 2 * n);
    st.point_update(i, kInf);
    st.point_update(i - n, kInf);
  };

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

  function<void(int)> find_height = [&](const int i) {
    assert(n <= i and i < 2 * n);
    while (st.query(i - k + 1, i - 1) == 0) {
      const int j = st.find_last_zero(i - k + 1, i - 1);
      find_height((j < n ? j + n : j));
    }
    h[i - n] = tall--;
    point_update(i);
    range_update(i);
  };

  while (tall >= 0) {
    assert(st.query(0, 2 * n - 1) == 0);
    const int i = st.find_last_zero(n, 2 * n - 1);
    find_height(i);
  }

  return h;
}

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

void init(const 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;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from plants.cpp:2:
plants.cpp: In member function 'void LazySegTree::push(int, int, int)':
plants.cpp:34:25: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<LazySegTree::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     assert(0 <= x and x < t.size());
      |                       ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 66 ms 3024 KB Output is correct
7 Correct 2252 ms 4648 KB Output is correct
8 Execution timed out 4070 ms 12004 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 1789 ms 3056 KB Output is correct
7 Execution timed out 4086 ms 65488 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 1789 ms 3056 KB Output is correct
7 Execution timed out 4086 ms 65488 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 4091 ms 2784 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 364 KB Output is correct
7 Correct 77 ms 852 KB Output is correct
8 Correct 1145 ms 1000 KB Output is correct
9 Correct 193 ms 852 KB Output is correct
10 Correct 1135 ms 1000 KB Output is correct
11 Correct 112 ms 844 KB Output is correct
12 Correct 314 ms 864 KB Output is correct
13 Correct 1552 ms 1080 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 60 ms 852 KB Output is correct
6 Execution timed out 4090 ms 12656 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 66 ms 3024 KB Output is correct
7 Correct 2252 ms 4648 KB Output is correct
8 Execution timed out 4070 ms 12004 KB Time limit exceeded
9 Halted 0 ms 0 KB -