oj.uz

Submission #669163

# Submission time Handle Problem Language Result Execution time Memory
669163 2022-12-05T21:01:15 Z evenvalue Comparing Plants (IOI20_plants) C++17
44 / 100
 532 ms 27484 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 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;
  }
};

vector<int> h;

void find_valid_arrangement(const int k, vector<int> &r) {
  const int n = r.size();
  r.insert(r.end(), r.begin(), r.end());

  int tall = n - 1;

  LazySegTree st(r);

  auto point_update = [&](const int i) {
    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);
  };

  h.assign(n, -1);

  function<void(int)> find_height = [&](const int i) {
    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) {
    const int i = st.find_last_zero(n, 2 * n - 1);
    find_height(i);
  }
}

void init(int k, vector<int> r) {
  find_valid_arrangement(k, r);
}

int compare_plants(int x, int y) {
  if (h[x] > h[y]) return 1;
  return -1;
}

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 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.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 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 53 ms 3116 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 53 ms 3160 KB Output is correct
11 Correct 51 ms 3264 KB Output is correct
12 Correct 54 ms 3244 KB Output is correct
13 Correct 54 ms 3140 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 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 53 ms 3116 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 53 ms 3160 KB Output is correct
11 Correct 51 ms 3264 KB Output is correct
12 Correct 54 ms 3244 KB Output is correct
13 Correct 54 ms 3140 KB Output is correct
14 Correct 83 ms 3532 KB Output is correct
15 Correct 521 ms 12044 KB Output is correct
16 Correct 82 ms 3532 KB Output is correct
17 Correct 519 ms 12036 KB Output is correct
18 Correct 428 ms 18236 KB Output is correct
19 Correct 389 ms 15908 KB Output is correct
20 Correct 474 ms 15824 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 0 ms 212 KB Output is correct
3 Correct 51 ms 3168 KB Output is correct
4 Correct 308 ms 14928 KB Output is correct
5 Correct 373 ms 15800 KB Output is correct
6 Correct 449 ms 15444 KB Output is correct
7 Correct 509 ms 15532 KB Output is correct
8 Correct 532 ms 15668 KB Output is correct
9 Correct 336 ms 16784 KB Output is correct
10 Correct 347 ms 16336 KB Output is correct
11 Correct 286 ms 27484 KB Output is correct
12 Correct 304 ms 15156 KB Output is correct
13 Correct 432 ms 23968 KB Output is correct

Subtask #5
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 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 Incorrect 1 ms 212 KB Output isn't correct
4 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 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -