Submission #992379

#	Time	Username	Problem	Language	Result	Execution time	Memory
992379		tch1cherin	Chessboard (IZhO18_chessboard)	C++17	47 / 100	2041 ms	13204 KiB

chessboard

#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 = numeric_limits<long long>::max();
  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 / 8
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30