oj.uz

Submission #668642

# Submission time Handle Problem Language Result Execution time Memory
668642 2022-12-04T10:32:58 Z evenvalue Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 14976 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);
    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) {
    assert(0 <= l and l <= r and r < n);
    return find_last_zero(0, 0, (int) n - 1, l, r);
  }

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

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

  int query(const int l, const int r) {
    assert(0 <= l and l <= r and r < n);
    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);
  }

  assert(count(h.begin(), h.end(), -1) == 0);
  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;
}

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 'int LazySegTree::find_last_zero(int, int)':
plants.cpp:130:36: warning: comparison of integer expressions of different signedness: 'const int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  130 |     assert(0 <= l and l <= r and r < n);
      |                                  ~~^~~
plants.cpp: In member function 'void LazySegTree::range_update(int, int)':
plants.cpp:135:36: warning: comparison of integer expressions of different signedness: 'const int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  135 |     assert(0 <= l and l <= r and r < n);
      |                                  ~~^~~
plants.cpp: In member function 'void LazySegTree::point_update(int, int)':
plants.cpp:140:25: warning: comparison of integer expressions of different signedness: 'const int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  140 |     assert(0 <= p and p < n);
      |                       ~~^~~
plants.cpp: In member function 'int LazySegTree::query(int, int)':
plants.cpp:145:36: warning: comparison of integer expressions of different signedness: 'const int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  145 |     assert(0 <= l and l <= r and r < n);
      |                                  ~~^~~

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 1 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 66 ms 4052 KB Output is correct
7 Correct 2266 ms 6752 KB Output is correct
8 Execution timed out 4049 ms 14976 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 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 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 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Runtime error 1 ms 428 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 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 1 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 66 ms 4052 KB Output is correct
7 Correct 2266 ms 6752 KB Output is correct
8 Execution timed out 4049 ms 14976 KB Time limit exceeded
9 Halted 0 ms 0 KB -