oj.uz

Submission #992378

# Submission time Handle Problem Language Result Execution time Memory
992378 2024-06-04T11:04:20 Z tch1cherin Chessboard (IZhO18_chessboard) C++17
39 / 100
 636 ms 7516 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct segment_tree {
  int size;
  vector<array<int, 2>> tree;
  vector<int> push;

  array<int, 2> merge(array<int, 2> a, array<int, 2> b) {
    return a[0] < b[0] ? a : (a[0] > b[0] ? b : array<int, 2> {a[0], a[1] + b[1]});
  }

  void apply(int x, int value) {
    tree[x][0] += value;
    push[x] += value;
  }

  void propagate(int x) {
    if (push[x] != 0) {
      apply(x * 2, push[x]);
      apply(x * 2 + 1, push[x]);
      push[x] = 0;
    }
  }

  segment_tree(int n) : size(2 << __lg(n)), tree(2 * size, {INF, 0}), push(2 * size) {
    fill(tree.begin() + size, tree.begin() + size + n, array<int, 2> {0, 1});
    for (int i = size - 1; i > 0; i--) {
      tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
    }
  }
  
  void update(int l, int r, int value) {
    if (l < r) {
      update(l, r, value, 1, 0, size);
    }
  }

  void update(int l, int r, int value, int x, int lx, int rx) {
    if (lx >= r || rx <= l) {
      return;
    } else if (lx >= l && rx <= r) {
      apply(x, value);
    } else {
      propagate(x);
      int mid = (lx + rx) / 2;
      update(l, r, value, x * 2, lx, mid);
      update(l, r, value, x * 2 + 1, mid, rx);
      tree[x] = merge(tree[x * 2], tree[x * 2 + 1]);
    }
  }

  int query() {
    return (tree[1][0] > 0 ? 0 : tree[1][1]);
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, K;
  cin >> N >> K;
  vector<vector<array<int, 3>>> rect(N + 1);
  for (int i = 0; i < K; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    x1--, y1--, y2--;
    rect[x1].push_back({y1, y2, 1});
    rect[x2].push_back({y1, y2, -1});
  }
  auto Even = [&](int L, int R, int d) {
    int l = L % (2 * d) >= d ? L + d - L % d : L;
    int r = R % (2 * d) >= d ? R - R % d - 1 : R;
    return l > r ? pair {0, -1} : pair {l / (2 * d) * d + l % (2 * d), r / (2 * d) * d + r % (2 * d)};
  };
  auto Odd = [&](int L, int R, int d) {
    int l = L % (2 * d) < d ? L + d - L % d : L;
    int r = R % (2 * d) < d ? R - R % d - 1 : R;
    return l > r ? pair {0, -1} : pair {l / (2 * d) * d + (l - d) % (2 * d), r / (2 * d) * d + (r - d) % (2 * d)};
  };
  long long answer = INF;
  for (int d = 1; d < N; d++) {
    if (N % d == 0) {
      int N_even = N / (2 * d) * d + min(d, N % (2 * d)), N_odd = N / (2 * d) * d + max(0, N % (2 * d) - d);
      segment_tree st_even(N_even), st_odd(N_odd);
      long long answer_e = 0, answer_o = 0;
      for (int i = 0; i < N; i++) {
        for (auto [j1, j2, t] : rect[i]) {
          auto [j1_e, j2_e] = Even(j1, j2, d);
          auto [j1_o, j2_o] = Odd(j1, j2, d);
          st_even.update(j1_e, j2_e + 1, t);
          st_odd.update(j1_o, j2_o + 1, t);
        }
        int cnt_e = st_even.query(), cnt_o = st_odd.query();
        int r = (i / d) % 2;
        answer_o += (r ? cnt_e : N_even - cnt_e) + (!r ? cnt_o : N_odd - cnt_o);
        answer_e += (!r ? cnt_e : N_even - cnt_e) + (r ? cnt_o : N_odd - cnt_o);
      }
      answer = min({answer, answer_e, answer_o});
    }
  }
  cout << answer << "\n";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 468 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 26 ms 1880 KB Output is correct
17 Correct 39 ms 5152 KB Output is correct
18 Correct 91 ms 5468 KB Output is correct
19 Correct 619 ms 5200 KB Output is correct
20 Correct 636 ms 5460 KB Output is correct
21 Correct 38 ms 4956 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 78 ms 2832 KB Output is correct
24 Correct 85 ms 5168 KB Output is correct
25 Correct 16 ms 856 KB Output is correct
26 Correct 53 ms 3412 KB Output is correct
27 Correct 96 ms 4440 KB Output is correct
28 Correct 92 ms 5208 KB Output is correct
29 Correct 15 ms 2396 KB Output is correct
30 Correct 3 ms 472 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 53 ms 7516 KB Output isn't correct
10 Halted 0 ms 0 KB -