oj.uz

답안 #624297

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624297 2022-08-07T17:28:30 Z evenvalue 자리 배치 (IOI18_seats) C++17
100 / 100
 2028 ms 110220 KB 
#include "seats.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;

template<class node, class F = std::function<node(const node &, const node &)>>
class SegTree {
  int n = 0;
  std::vector<node> t;
  F unite;

  void build(const int x, const int l, const int r, const std::vector<node> &a) {
    if (l == r) {
      t[x] = a[l];
      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]);
  }

  void update(const int x, const int l, const int r, const int p, const node &v) {
    if (l == p and p == r) {
      t[x] = v;
      return;
    }
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (p <= mid) {
      update(x + 1, l, mid, p, v);
    } else {
      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) const {
    if (ql <= l and r <= qr) {
      return t[x];
    }
    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));
    }
  }

  void debug_node(const int x, const vector<int> &path) const {
    for (int i = 0; i < path.size(); i++) {
      cerr << path[i] << (i == path.size() - 1 ? ": " : " -> ");
    }
    cerr << t[x] << '\n';
  }

  void debug(const int x, const int l, const int r, vector<int> path) const {
    path.push_back(x);
    if (l == r) {
      debug_node(x, path);
      return;
    }
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    debug(x + 1, l, mid, path);
    debug(y, mid + 1, r, path);
    debug_node(x, path);
  }

public:
  SegTree() = default;
  explicit SegTree(const int n, const node e, F f) : n(n), t(2 * n - 1, e), unite(std::move(f)) {}
  explicit SegTree(const std::vector<node> &a, F f) : n(a.size()), t(2 * (a.size()) - 1), unite(std::move(f)) {
    build(0, 0, n - 1, a);
  }

  void set(const int p, const node &v) {
    assert(0 <= p and p < n);
    update(0, 0, n - 1, p, v);
  }

  [[nodiscard]] node get(const int l, const int r) const {
    assert(0 <= l and l <= r and r < n);
    return query(0, 0, n - 1, l, r);
  }

  void debug() const {
    debug(0, 0, n - 1, {});
    cerr << "----------\n\n";
  }
};

struct node {
  int sum = 0;
  int mini = 0;
  int cnt = 0;

  friend ostream &operator<<(ostream &os, const node &x);
};

ostream &operator<<(ostream &os, const node &x) {
  os << x.sum << ' ' << x.mini << ' ' << x.cnt;
  return os;
}

int n, m, total_seats;
vector<int> R, C;
SegTree<node> st;
vector<vector<int>> grid;

const vector<pair<int, int>> tr = {
    {-1, -1},
    {-1, 0},
    {0, -1},
    {0, 0}};
const vector<pair<int, int>> nbr = {
    {0, 0},
    {0, 1},
    {1, 0},
    {1, 1}};

bool exists(const int row, const int col) {
  return (0 <= row and row < n and 0 <= col and col < m);
}

int calc_delta(const int x) {
  const int row = R[x], col = C[x];

  int delta = 0;
  vector<int> v;
  for (auto [r, c] : tr) {
    r += R[x], c += C[x];
    for (const auto &[dr, dc] : nbr) {
      if (not exists(r + dr, c + dc)) continue;
      v.push_back(grid[r + dr][c + dc]);
    }
    sort(v.begin(), v.end());
    const int pos = distance(v.begin(), find(v.begin(), v.end(), grid[row][col]));
    if (pos == 0) delta++;
    if (pos == 1) delta--;
    if (pos == 2) delta++;
    if (pos == 3) delta--;
    v.clear();
  }
  return delta;
}

void give_initial_chart(const int H, const int W, std::vector<int> R_, std::vector<int> C_) {
  n = H, m = W;
  total_seats = n * m;
  R = move(R_), C = move(C_);
  grid.resize(n, vector<int>(m));
  st = SegTree<node>(total_seats, node(), [&](const node &l, const node &r) {
    node ret{};
    ret.sum = l.sum + r.sum;
    if (l.mini == l.sum + r.mini) {
      ret.mini = l.mini;
      ret.cnt = l.cnt + r.cnt;
    } else if (l.mini < l.sum + r.mini) {
      ret.mini = l.mini;
      ret.cnt = l.cnt;
    } else {
      ret.mini = l.sum + r.mini;
      ret.cnt = r.cnt;
    }
    return ret;
  });

  for (int seat = 0; seat < total_seats; seat++) {
    grid[R[seat]][C[seat]] = seat;
  }

  for (int seat = 0; seat < total_seats; seat++) {
    const int delta = calc_delta(seat);
    st.set(seat, {delta, delta, 1});
  }
}

int swap_seats(const int x, const int y) {
  swap(grid[R[x]][C[x]], grid[R[y]][C[y]]);
  swap(R[x], R[y]);
  swap(C[x], C[y]);
  for (const int pt : {x, y}) {
    for (auto [r, c] : tr) {
      r += R[pt], c += C[pt];
      for (const auto &[dr, dc] : nbr) {
        if (not exists(r + dr, c + dc)) continue;
        const int seat = grid[r + dr][c + dc];
        const int delta = calc_delta(seat);
        st.set(seat, {delta, delta, 1});
      }
    }
  }
  return st.get(0,total_seats - 1).cnt;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 416 KB Output is correct
2 Correct 45 ms 428 KB Output is correct
3 Correct 57 ms 392 KB Output is correct
4 Correct 24 ms 460 KB Output is correct
5 Correct 22 ms 448 KB Output is correct
6 Correct 46 ms 460 KB Output is correct
7 Correct 55 ms 440 KB Output is correct
8 Correct 52 ms 400 KB Output is correct
9 Correct 53 ms 408 KB Output is correct
10 Correct 54 ms 404 KB Output is correct
11 Correct 44 ms 412 KB Output is correct
12 Correct 23 ms 444 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 416 KB Output is correct
2 Correct 45 ms 428 KB Output is correct
3 Correct 57 ms 392 KB Output is correct
4 Correct 24 ms 460 KB Output is correct
5 Correct 22 ms 448 KB Output is correct
6 Correct 46 ms 460 KB Output is correct
7 Correct 55 ms 440 KB Output is correct
8 Correct 52 ms 400 KB Output is correct
9 Correct 53 ms 408 KB Output is correct
10 Correct 54 ms 404 KB Output is correct
11 Correct 44 ms 412 KB Output is correct
12 Correct 23 ms 444 KB Output is correct
13 Correct 88 ms 1004 KB Output is correct
14 Correct 92 ms 956 KB Output is correct
15 Correct 39 ms 980 KB Output is correct
16 Correct 36 ms 1488 KB Output is correct
17 Correct 68 ms 968 KB Output is correct
18 Correct 76 ms 964 KB Output is correct
19 Correct 74 ms 996 KB Output is correct
20 Correct 61 ms 1192 KB Output is correct
21 Correct 37 ms 996 KB Output is correct
22 Correct 37 ms 1476 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 952 ms 59400 KB Output is correct
2 Correct 855 ms 59432 KB Output is correct
3 Correct 814 ms 59416 KB Output is correct
4 Correct 817 ms 59432 KB Output is correct
5 Correct 822 ms 59404 KB Output is correct
6 Correct 827 ms 59468 KB Output is correct
7 Correct 810 ms 59388 KB Output is correct
8 Correct 818 ms 59440 KB Output is correct
9 Correct 828 ms 59388 KB Output is correct
10 Correct 810 ms 59468 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 980 KB Output is correct
2 Correct 146 ms 5524 KB Output is correct
3 Correct 851 ms 59444 KB Output is correct
4 Correct 934 ms 59468 KB Output is correct
5 Correct 702 ms 59400 KB Output is correct
6 Correct 1041 ms 110220 KB Output is correct
7 Correct 818 ms 59380 KB Output is correct
8 Correct 875 ms 59428 KB Output is correct
9 Correct 810 ms 59740 KB Output is correct
10 Correct 844 ms 62484 KB Output is correct
11 Correct 820 ms 82860 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 2148 KB Output is correct
2 Correct 183 ms 1952 KB Output is correct
3 Correct 236 ms 2016 KB Output is correct
4 Correct 278 ms 2092 KB Output is correct
5 Correct 328 ms 2724 KB Output is correct
6 Correct 1108 ms 61148 KB Output is correct
7 Correct 1132 ms 61268 KB Output is correct
8 Correct 1085 ms 61148 KB Output is correct
9 Correct 1163 ms 61080 KB Output is correct
10 Correct 1037 ms 61208 KB Output is correct
11 Correct 1067 ms 61204 KB Output is correct
12 Correct 1012 ms 61096 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 416 KB Output is correct
2 Correct 45 ms 428 KB Output is correct
3 Correct 57 ms 392 KB Output is correct
4 Correct 24 ms 460 KB Output is correct
5 Correct 22 ms 448 KB Output is correct
6 Correct 46 ms 460 KB Output is correct
7 Correct 55 ms 440 KB Output is correct
8 Correct 52 ms 400 KB Output is correct
9 Correct 53 ms 408 KB Output is correct
10 Correct 54 ms 404 KB Output is correct
11 Correct 44 ms 412 KB Output is correct
12 Correct 23 ms 444 KB Output is correct
13 Correct 88 ms 1004 KB Output is correct
14 Correct 92 ms 956 KB Output is correct
15 Correct 39 ms 980 KB Output is correct
16 Correct 36 ms 1488 KB Output is correct
17 Correct 68 ms 968 KB Output is correct
18 Correct 76 ms 964 KB Output is correct
19 Correct 74 ms 996 KB Output is correct
20 Correct 61 ms 1192 KB Output is correct
21 Correct 37 ms 996 KB Output is correct
22 Correct 37 ms 1476 KB Output is correct
23 Correct 952 ms 59400 KB Output is correct
24 Correct 855 ms 59432 KB Output is correct
25 Correct 814 ms 59416 KB Output is correct
26 Correct 817 ms 59432 KB Output is correct
27 Correct 822 ms 59404 KB Output is correct
28 Correct 827 ms 59468 KB Output is correct
29 Correct 810 ms 59388 KB Output is correct
30 Correct 818 ms 59440 KB Output is correct
31 Correct 828 ms 59388 KB Output is correct
32 Correct 810 ms 59468 KB Output is correct
33 Correct 82 ms 980 KB Output is correct
34 Correct 146 ms 5524 KB Output is correct
35 Correct 851 ms 59444 KB Output is correct
36 Correct 934 ms 59468 KB Output is correct
37 Correct 702 ms 59400 KB Output is correct
38 Correct 1041 ms 110220 KB Output is correct
39 Correct 818 ms 59380 KB Output is correct
40 Correct 875 ms 59428 KB Output is correct
41 Correct 810 ms 59740 KB Output is correct
42 Correct 844 ms 62484 KB Output is correct
43 Correct 820 ms 82860 KB Output is correct
44 Correct 152 ms 2148 KB Output is correct
45 Correct 183 ms 1952 KB Output is correct
46 Correct 236 ms 2016 KB Output is correct
47 Correct 278 ms 2092 KB Output is correct
48 Correct 328 ms 2724 KB Output is correct
49 Correct 1108 ms 61148 KB Output is correct
50 Correct 1132 ms 61268 KB Output is correct
51 Correct 1085 ms 61148 KB Output is correct
52 Correct 1163 ms 61080 KB Output is correct
53 Correct 1037 ms 61208 KB Output is correct
54 Correct 1067 ms 61204 KB Output is correct
55 Correct 1012 ms 61096 KB Output is correct
56 Correct 352 ms 1952 KB Output is correct
57 Correct 580 ms 2056 KB Output is correct
58 Correct 747 ms 2580 KB Output is correct
59 Correct 1757 ms 61112 KB Output is correct
60 Correct 2028 ms 61020 KB Output is correct
61 Correct 1606 ms 60988 KB Output is correct
62 Correct 1354 ms 61200 KB Output is correct
63 Correct 1781 ms 61228 KB Output is correct
64 Correct 1721 ms 61236 KB Output is correct
65 Correct 1605 ms 61000 KB Output is correct
66 Correct 1763 ms 61388 KB Output is correct
67 Correct 1702 ms 64076 KB Output is correct
68 Correct 1492 ms 75308 KB Output is correct
69 Correct 1823 ms 84408 KB Output is correct