oj.uz

Submission #669164

# Submission time Handle Problem Language Result Execution time Memory
669164 2022-12-05T21:03:33 Z evenvalue Comparing Plants (IOI20_plants) C++17
100 / 100
 1732 ms 119932 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) {
    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) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (t[y].val == 0) {
      return find_last_zero(y, mid + 1, r);
    } else {
      return find_last_zero(x + 1, l, mid);
    }
  }

  int find_last_zero(const int x, const int l, const int r, const int ql, const int qr) {
    if (ql <= l and r <= qr) {
      return find_last_zero(x, l, r);
    }
    push(x, l, r);
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (mid < qr and t[y].val == 0) {
      const int ans = find_last_zero(y, mid + 1, r, ql, qr);
      if (ans != -1) return ans;
    }
    if (ql <= mid and t[x + 1].val == 0) {
      return find_last_zero(x + 1, l, mid, ql, qr);
    }
    return -1;
  }

  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;
}

Subtask #1
5.0 / 5.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 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 74 ms 3728 KB Output is correct
7 Correct 209 ms 13484 KB Output is correct
8 Correct 735 ms 101524 KB Output is correct
9 Correct 809 ms 103864 KB Output is correct
10 Correct 859 ms 104220 KB Output is correct
11 Correct 915 ms 106140 KB Output is correct
12 Correct 938 ms 110284 KB Output is correct
13 Correct 865 ms 116384 KB Output is correct
14 Correct 918 ms 103924 KB Output is correct

Subtask #2
14.0 / 14.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 1 ms 296 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 976 KB Output is correct
7 Correct 105 ms 6232 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 5 ms 956 KB Output is correct
10 Correct 92 ms 6236 KB Output is correct
11 Correct 101 ms 6244 KB Output is correct
12 Correct 136 ms 6188 KB Output is correct
13 Correct 85 ms 6272 KB Output is correct

Subtask #3
13.0 / 13.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 1 ms 296 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 976 KB Output is correct
7 Correct 105 ms 6232 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 5 ms 956 KB Output is correct
10 Correct 92 ms 6236 KB Output is correct
11 Correct 101 ms 6244 KB Output is correct
12 Correct 136 ms 6188 KB Output is correct
13 Correct 85 ms 6272 KB Output is correct
14 Correct 177 ms 14168 KB Output is correct
15 Correct 1732 ms 112856 KB Output is correct
16 Correct 189 ms 14204 KB Output is correct
17 Correct 1725 ms 112896 KB Output is correct
18 Correct 1086 ms 116796 KB Output is correct
19 Correct 1314 ms 110656 KB Output is correct
20 Correct 1672 ms 119932 KB Output is correct

Subtask #4
17.0 / 17.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 105 ms 4488 KB Output is correct
4 Correct 1110 ms 104292 KB Output is correct
5 Correct 1156 ms 101864 KB Output is correct
6 Correct 1262 ms 101420 KB Output is correct
7 Correct 1352 ms 102092 KB Output is correct
8 Correct 1584 ms 109584 KB Output is correct
9 Correct 1020 ms 102876 KB Output is correct
10 Correct 1063 ms 102556 KB Output is correct
11 Correct 906 ms 113628 KB Output is correct
12 Correct 1028 ms 101268 KB Output is correct
13 Correct 1121 ms 115628 KB Output is correct

Subtask #5
11.0 / 11.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 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 440 KB Output is correct
7 Correct 20 ms 1364 KB Output is correct
8 Correct 18 ms 1332 KB Output is correct
9 Correct 21 ms 1260 KB Output is correct
10 Correct 16 ms 1408 KB Output is correct
11 Correct 19 ms 1304 KB Output is correct
12 Correct 19 ms 1356 KB Output is correct
13 Correct 14 ms 1336 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 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 4 ms 724 KB Output is correct
6 Correct 974 ms 101536 KB Output is correct
7 Correct 1058 ms 101944 KB Output is correct
8 Correct 1058 ms 102548 KB Output is correct
9 Correct 1519 ms 110232 KB Output is correct
10 Correct 928 ms 103480 KB Output is correct
11 Correct 1008 ms 111800 KB Output is correct
12 Correct 894 ms 106684 KB Output is correct
13 Correct 1020 ms 104084 KB Output is correct
14 Correct 952 ms 103596 KB Output is correct
15 Correct 1166 ms 104580 KB Output is correct
16 Correct 791 ms 104876 KB Output is correct
17 Correct 871 ms 103448 KB Output is correct

Subtask #7
25.0 / 25.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 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 74 ms 3728 KB Output is correct
7 Correct 209 ms 13484 KB Output is correct
8 Correct 735 ms 101524 KB Output is correct
9 Correct 809 ms 103864 KB Output is correct
10 Correct 859 ms 104220 KB Output is correct
11 Correct 915 ms 106140 KB Output is correct
12 Correct 938 ms 110284 KB Output is correct
13 Correct 865 ms 116384 KB Output is correct
14 Correct 918 ms 103924 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 296 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 5 ms 976 KB Output is correct
21 Correct 105 ms 6232 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 5 ms 956 KB Output is correct
24 Correct 92 ms 6236 KB Output is correct
25 Correct 101 ms 6244 KB Output is correct
26 Correct 136 ms 6188 KB Output is correct
27 Correct 85 ms 6272 KB Output is correct
28 Correct 177 ms 14168 KB Output is correct
29 Correct 1732 ms 112856 KB Output is correct
30 Correct 189 ms 14204 KB Output is correct
31 Correct 1725 ms 112896 KB Output is correct
32 Correct 1086 ms 116796 KB Output is correct
33 Correct 1314 ms 110656 KB Output is correct
34 Correct 1672 ms 119932 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 105 ms 4488 KB Output is correct
38 Correct 1110 ms 104292 KB Output is correct
39 Correct 1156 ms 101864 KB Output is correct
40 Correct 1262 ms 101420 KB Output is correct
41 Correct 1352 ms 102092 KB Output is correct
42 Correct 1584 ms 109584 KB Output is correct
43 Correct 1020 ms 102876 KB Output is correct
44 Correct 1063 ms 102556 KB Output is correct
45 Correct 906 ms 113628 KB Output is correct
46 Correct 1028 ms 101268 KB Output is correct
47 Correct 1121 ms 115628 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 3 ms 440 KB Output is correct
54 Correct 20 ms 1364 KB Output is correct
55 Correct 18 ms 1332 KB Output is correct
56 Correct 21 ms 1260 KB Output is correct
57 Correct 16 ms 1408 KB Output is correct
58 Correct 19 ms 1304 KB Output is correct
59 Correct 19 ms 1356 KB Output is correct
60 Correct 14 ms 1336 KB Output is correct
61 Correct 105 ms 5688 KB Output is correct
62 Correct 257 ms 14992 KB Output is correct
63 Correct 973 ms 103708 KB Output is correct
64 Correct 1157 ms 103992 KB Output is correct
65 Correct 1192 ms 104276 KB Output is correct
66 Correct 1270 ms 105316 KB Output is correct
67 Correct 1499 ms 113004 KB Output is correct
68 Correct 1059 ms 105836 KB Output is correct
69 Correct 1178 ms 112656 KB Output is correct
70 Correct 1124 ms 107284 KB Output is correct
71 Correct 1309 ms 104724 KB Output is correct
72 Correct 1242 ms 104356 KB Output is correct
73 Correct 1340 ms 105428 KB Output is correct
74 Correct 994 ms 103968 KB Output is correct
75 Correct 962 ms 104500 KB Output is correct