oj.uz

Submission #668679

# Submission time Handle Problem Language Result Execution time Memory
668679 2022-12-04T12:19:52 Z evenvalue Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 21704 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});
  };

  {
    const auto r_ = r;
    r.insert(r.end(), r_.begin(), r_.end());
    r.insert(r.end(), r_.begin(), r_.end());
  }

  g.assign(n, vector<int>(0));
  set<pair<int, int>> left, right;

  left.insert({-1, -1});
  for (int i = n - k + 1; i < n; i++) {
    left.insert({h[i], i});
  }

  right.insert({-1, -1});
  for (int i = n + 1; i < n + k; i++) {
    right.insert({h[i % n], i});
  }

  for (int i = n; i < 2 * n; i++) {
    const int x = i - n;
    {
      auto [ht, y] = *prev(left.lower_bound(make_pair(h[x], x)));
      if (y != -1) g[x].push_back(y % n);
    }
    {
      auto [ht, y] = *prev(right.lower_bound(make_pair(h[x], x)));
      if (y != -1) g[x].push_back(y % n);
    }
    {
      left.erase({h[(i - k + 1) % n], i - k + 1});
      right.erase({h[(i + 1) % n], i + 1});

      left.insert({h[x], i});
      right.insert({h[(i + k) % n], i + k});
    }
  }
}

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());
      |                       ~~^~~~~~~~~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:199:8: warning: variable 'dist' set but not used [-Wunused-but-set-variable]
  199 |   auto dist = [&](const int i, const int j) {
      |        ^~~~

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 0 ms 212 KB Output is correct
6 Correct 65 ms 3048 KB Output is correct
7 Correct 1176 ms 4372 KB Output is correct
8 Execution timed out 4070 ms 12048 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 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 83 ms 512 KB Output is correct
7 Execution timed out 4043 ms 3532 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 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 83 ms 512 KB Output is correct
7 Execution timed out 4043 ms 3532 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 3383 ms 3236 KB Output is correct
4 Execution timed out 4017 ms 21704 KB Time limit exceeded
5 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 1 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 5 ms 340 KB Output is correct
7 Correct 48 ms 852 KB Output is correct
8 Correct 139 ms 840 KB Output is correct
9 Correct 115 ms 852 KB Output is correct
10 Correct 147 ms 972 KB Output is correct
11 Correct 69 ms 852 KB Output is correct
12 Correct 121 ms 852 KB Output is correct
13 Correct 156 ms 876 KB Output is correct

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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 13 ms 380 KB Output is correct
6 Execution timed out 4070 ms 15088 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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 65 ms 3048 KB Output is correct
7 Correct 1176 ms 4372 KB Output is correct
8 Execution timed out 4070 ms 12048 KB Time limit exceeded
9 Halted 0 ms 0 KB -