oj.uz

Submission #669110

# Submission time Handle Problem Language Result Execution time Memory
669110 2022-12-05T18:38:32 Z evenvalue Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 112516 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;
constexpr int kLogN = 20;

class LazySegTree {
  struct Node {
    int val = kInf;
    int inc = 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.inc = 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].inc;
      t[child].inc += t[x].inc;
    }
    t[x].inc = 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].inc = 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 update(const int x, const int l, const int r, const int ql, const int qr, const int value) {
    if (ql <= l and r <= qr) {
      t[x].val += value;
      t[x].inc += value;
      return;
    }
    push(x, l, r);
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (ql <= mid) {
      update(x + 1, l, mid, ql, qr, value);
    }
    if (mid < qr) {
      update(y, mid + 1, r, ql, qr, value);
    }
    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 update(const int l, const int r, const int x) {
    update(0, 0, (int) n - 1, l, r, x);
  }

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

//Global Variables
int n = 0;
int k = 0;
vector<int> h;
vector<vector<int>> go_left, left_dist;
vector<vector<int>> go_right, right_dist;

vector<int> find_valid_arrangement(vector<int> r) {
  r.insert(r.end(), r.begin(), r.end());

  h.resize(n);
  int tall = n - 1;

  LazySegTree st(r);

  auto point_update = [&](const int i) {
    assert(n <= i and i < 2 * n);
    st.update(i, i, kInf);
    st.update(i - n, i - n, kInf);
  };

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

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

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

  go_left.assign(n, vector<int>(kLogN));
  go_right.assign(n, vector<int>(kLogN));
  left_dist.assign(n, vector<int>(kLogN));
  right_dist.assign(n, vector<int>(kLogN));

  set<pair<int, int>> lt, rt;

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

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

  for (int i = n; i < 2 * n; i++) {
    const int x = i - n;
    {
      auto [ht, y] = *prev(lt.lower_bound(make_pair(h[x], x)));
      go_left[x][0] = (y == -1 ? x : y % n);
      left_dist[x][0] = (y == -1 ? kInf : i - y);
    }
    {
      auto [ht, y] = *prev(rt.lower_bound(make_pair(h[x], x)));
      go_right[x][0] = (y == -1 ? x : y % n);
      right_dist[x][0] = (y == -1 ? kInf : y - i);
    }
    {
      lt.erase({h[(i - k + 1) % n], i - k + 1});
      rt.erase({h[(i + 1) % n], i + 1});

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

  for (int i = 1; i < kLogN; i++) {
    for (int x = 0; x < n; x++) {
      const int mid = go_left[x][i - 1];
      go_left[x][i] = go_left[mid][i - 1];
      left_dist[x][i] = min(kInf, left_dist[x][i - 1] + left_dist[mid][i - 1]);
    }
  }

  for (int i = 1; i < kLogN; i++) {
    for (int x = 0; x < n; x++) {
      const int mid = go_right[x][i - 1];
      go_right[x][i] = go_right[mid][i - 1];
      right_dist[x][i] = min(kInf, right_dist[x][i - 1] + right_dist[mid][i - 1]);
    }
  }
}

bool can_go_left(int x, const int y) {
  int d = (x >= y ? x - y : x + n - y);
  for (int j = kLogN - 1; j >= 0; j--) {
    if (d < left_dist[x][j]) continue;
    d -= left_dist[x][j];
    x = go_left[x][j];
  }
  return (d < k and h[x] >= h[y]);
}

bool can_go_right(int x, const int y) {
  int d = (x <= y ? y - x : y + n - x);
  for (int j = kLogN - 1; j >= 0; j--) {
    if (d < right_dist[x][j]) continue;
    d -= right_dist[x][j];
    x = go_right[x][j];
  }
  return (d < k and h[x] >= h[y]);
}

bool can_go(const int s, const int t) {
  return can_go_left(s, t) or can_go_right(s, 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:35:25: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<LazySegTree::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     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 1 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 67 ms 3084 KB Output is correct
7 Correct 695 ms 12920 KB Output is correct
8 Execution timed out 4046 ms 15744 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 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 1 ms 340 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 85 ms 5840 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 91 ms 5940 KB Output is correct
11 Correct 146 ms 6060 KB Output is correct
12 Correct 137 ms 5832 KB Output is correct
13 Correct 87 ms 5828 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 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 1 ms 340 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 85 ms 5840 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 91 ms 5940 KB Output is correct
11 Correct 146 ms 6060 KB Output is correct
12 Correct 137 ms 5832 KB Output is correct
13 Correct 87 ms 5828 KB Output is correct
14 Correct 183 ms 13912 KB Output is correct
15 Correct 1667 ms 112516 KB Output is correct
16 Correct 199 ms 13784 KB Output is correct
17 Correct 1785 ms 112516 KB Output is correct
18 Execution timed out 4067 ms 13564 KB Time limit exceeded
19 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 0 ms 212 KB Output is correct
3 Correct 102 ms 4072 KB Output is correct
4 Execution timed out 4035 ms 20936 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 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 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 19 ms 980 KB Output is correct
8 Correct 16 ms 1336 KB Output is correct
9 Correct 19 ms 1336 KB Output is correct
10 Correct 15 ms 1364 KB Output is correct
11 Correct 19 ms 1296 KB Output is correct
12 Correct 19 ms 1356 KB Output is correct
13 Correct 17 ms 1328 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 4 ms 724 KB Output is correct
6 Correct 1137 ms 103248 KB Output is correct
7 Correct 1094 ms 103592 KB Output is correct
8 Correct 1177 ms 104464 KB Output is correct
9 Correct 1523 ms 112272 KB Output is correct
10 Execution timed out 4069 ms 17672 KB Time limit exceeded
11 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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 67 ms 3084 KB Output is correct
7 Correct 695 ms 12920 KB Output is correct
8 Execution timed out 4046 ms 15744 KB Time limit exceeded
9 Halted 0 ms 0 KB -