oj.uz

Submission #669111

# Submission time Handle Problem Language Result Execution time Memory
669111 2022-12-05T18:39:18 Z evenvalue Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 100032 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 = 18;

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 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 60 ms 3100 KB Output is correct
7 Correct 650 ms 11664 KB Output is correct
8 Execution timed out 4048 ms 12836 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
14.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 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 91 ms 5532 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 87 ms 5600 KB Output is correct
11 Correct 185 ms 5588 KB Output is correct
12 Correct 126 ms 5684 KB Output is correct
13 Correct 90 ms 5724 KB Output is correct

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 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 91 ms 5532 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 87 ms 5600 KB Output is correct
11 Correct 185 ms 5588 KB Output is correct
12 Correct 126 ms 5684 KB Output is correct
13 Correct 90 ms 5724 KB Output is correct
14 Correct 171 ms 12584 KB Output is correct
15 Correct 1708 ms 100032 KB Output is correct
16 Correct 182 ms 12548 KB Output is correct
17 Correct 1760 ms 99988 KB Output is correct
18 Execution timed out 4058 ms 13408 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 96 ms 3940 KB Output is correct
4 Execution timed out 4091 ms 18108 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 1 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 21 ms 960 KB Output is correct
8 Correct 15 ms 996 KB Output is correct
9 Correct 18 ms 980 KB Output is correct
10 Correct 14 ms 980 KB Output is correct
11 Correct 18 ms 980 KB Output is correct
12 Correct 17 ms 980 KB Output is correct
13 Correct 13 ms 988 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 3 ms 724 KB Output is correct
6 Correct 1106 ms 88336 KB Output is correct
7 Correct 1072 ms 88736 KB Output is correct
8 Correct 1068 ms 89488 KB Output is correct
9 Correct 1545 ms 97128 KB Output is correct
10 Execution timed out 4009 ms 15632 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 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 60 ms 3100 KB Output is correct
7 Correct 650 ms 11664 KB Output is correct
8 Execution timed out 4048 ms 12836 KB Time limit exceeded
9 Halted 0 ms 0 KB -