Submission #844109

#	Time	Username	Problem	Language	Result	Execution time	Memory
844109		zwezdinv	Chessboard (IZhO18_chessboard)	C++17	47 / 100	2041 ms	12116 KiB

chessboard

#include<bits/stdc++.h>

using namespace std;
#define all(x) x.begin(), x.end()
using ll = long long;

const int N = 2e5;

int cnt0[4 * N], cnt1[4 * N];
bool upd[4 * N];

void push(int node) {
    if (!upd[node]) return;
    swap(cnt0[node], cnt1[node]);
    upd[node << 1] = !upd[node << 1];
    upd[node << 1 | 1] = !upd[node << 1 | 1];
    upd[node] = 0;
}

int n;

void reset(int node = 1, int l = 0, int r = n - 1) {
    upd[node] = 0;
    if (l == r) {
        cnt0[node] = 1;
        cnt1[node] = 0;
        return;
    }
    int m = (l + r) / 2;
    reset(node << 1, l, m);
    reset(node << 1 | 1, m + 1, r);
    cnt0[node] = cnt0[node << 1] + cnt0[node << 1 | 1];
    cnt1[node] = cnt1[node << 1] + cnt1[node << 1 | 1];
}
void flip(int ql, int qr, int node = 1, int l = 0, int r = n - 1) {
    push(node);
    if (r < ql || qr < l) return;
    if (ql <= l && r <= qr) {
        upd[node] = !upd[node];
        push(node);
        return;
    }
    int m = (l + r) / 2;
    flip(ql, qr, node << 1, l, m);
    flip(ql, qr, node << 1 | 1, m + 1, r);
    cnt0[node] = cnt0[node << 1] + cnt0[node << 1 | 1];
    cnt1[node] = cnt1[node << 1] + cnt1[node << 1 | 1];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int k;
    cin >> n >> k;
    vector<vector<pair<int, int>>> ev(n + 1);
    for (int i = 0; i < k; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        --x1, --y1, --x2, --y2;
        ev[x1].emplace_back(y1, y2);
        ev[x2 + 1].emplace_back(y1, y2);
    }
    ll res = 1e18;
    for (int d = 1; d < n; ++d) {
        if (n % d == 0) {
            {
                ll ans = 0;
                reset();
                for (int i = 0; i < n; i += d * 2) {
                    flip(i, i + d - 1);
                }
                for (int i = 0; i < n; ++i) {
                    if (i % d == 0) {
                        flip(0, n - 1);
                    }
                    for (auto [x, y]: ev[i]) {
                        flip(x, y);
                    }
                    ans += cnt1[1];
                }
                res = min(res, ans);
            }
            {
                ll ans = 0;
                reset();
                for (int i = d; i < n; i += d * 2) {
                    flip(i, i + d - 1);
                }
                for (int i = 0; i < n; ++i) {
                    if (i % d == 0) {
                        flip(0, n - 1);
                    }
                    for (auto [x, y]: ev[i]) {
                        flip(x, y);
                    }
                    ans += cnt1[1];
                }
                res = min(res, ans);
            }
        }
    }
    cout << res;
}

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