oj.uz

답안 #668672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
668672 2022-12-04T11:57:35 Z evenvalue 식물 비교 (IOI20_plants) C++17
11 / 100
 4000 ms 65456 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--;
      if (t[x].val == -1) {

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

  g.assign(n, vector<int>(0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (h[i] <= h[j] or dist(i, j) >= k) continue;
      g[i].push_back(j);
    }
  }
}

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());
      |                       ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 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 60 ms 3036 KB Output is correct
7 Correct 2233 ms 4412 KB Output is correct
8 Execution timed out 4067 ms 12120 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 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 3 ms 212 KB Output is correct
6 Correct 1682 ms 3060 KB Output is correct
7 Execution timed out 4061 ms 65456 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 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 3 ms 212 KB Output is correct
6 Correct 1682 ms 3060 KB Output is correct
7 Execution timed out 4061 ms 65456 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 4049 ms 4520 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 1 ms 212 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 75 ms 1164 KB Output is correct
8 Correct 1137 ms 1320 KB Output is correct
9 Correct 193 ms 1176 KB Output is correct
10 Correct 1146 ms 1336 KB Output is correct
11 Correct 112 ms 1172 KB Output is correct
12 Correct 334 ms 1188 KB Output is correct
13 Correct 1540 ms 1428 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 62 ms 908 KB Output is correct
6 Execution timed out 4059 ms 14892 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 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 60 ms 3036 KB Output is correct
7 Correct 2233 ms 4412 KB Output is correct
8 Execution timed out 4067 ms 12120 KB Time limit exceeded
9 Halted 0 ms 0 KB -