Submission #503163

#	Time	Username	Problem	Language	Result	Execution time	Memory
503163		Pety	Chessboard (IZhO18_chessboard)	C++14	100 / 100	340 ms	9548 KiB

chessboard

#include <bits/stdc++.h>
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ll long long
#define ld long double

using namespace std;

const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const int N = 1e5 + 2;

int n, sum[100002], k, lazy[400002], aint[400002], l[400002], r[400002];

struct query {
  int type, l, r;
  bool operator < (const query &other) {
    return type < other.type;
  }
};
vector<query>q[100002];


int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> k;
  while (k--) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    x1--; y1--; x2--; y2--;
    q[x1].push_back({1, y1, y2});
    q[x2 + 1].push_back({0, y1, y2});
  }
  for (int i = 0; i < n; i++)
    sort(q[i].begin(), q[i].end());
  ll sol = 1ll * n * n, div = 0;;
  for (int lat = 1; lat < n; lat++) {
    if (n % lat == 0) {
      div++;
      for (int i = 0; i < n; i++) {
        sum[i] = ((i / lat) & 1) + (i > 0 ? sum[i - 1] : 0);
      }
      ll  lin = sum[n - 1], nr = 0;
      for (int i = 0; i < n; i++) {
        for (auto it : q[i]) {
          if (it.type == 0) {
            lin = lin - (it.r - it.l + 1) + 2 * (sum[it.r] - (it.l > 0 ? sum[it.l - 1] : 0));
          }
          else {
            lin = lin + (it.r - it.l + 1) - 2 * (sum[it.r] - (it.l > 0 ? sum[it.l - 1] : 0));
          }
        }
        if ((i / lat) & 1)
          nr +=  n - lin;
        else
          nr += lin;
      }
      sol = min(sol, min(nr, 1l * n  * n - nr));
    }
  }
  cout << sol;
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 23 / 23
• Subtask 6: 30 / 30