제출 #523560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523560		RaresFelix	Chessboard (IZhO18_chessboard)	C++17	47 / 100	2086 ms	7620 KiB

chessboard

#include <vector>
#include <iostream>
#include <climits>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define MN 107171
using ll = long long;
using namespace std;
int n, k;

namespace AINT {
    int V[3 * MN];
    bool LZ[3 * MN];
    void clear(const int &u = 1, const int &s = 1, const int &d = n) {
        V[u] = LZ[u] = 0;
        if(s != d)
            clear(u * 2, s, (s + d) /2), clear(u * 2 + 1, (s + d) / 2 + 1, d);
    }
    static inline void prp(const int &u, const int &s, const int &d) {
        if(!LZ[u]) return;
        V[u] = d - s + 1 - V[u];
        LZ[u] = 0;
        if(s != d)
            LZ[u * 2] ^= 1, LZ[u * 2 + 1] ^= 1;
    }
    void update(const int &l, const int &r, int u = 1, int s = 1, int d = n) {
        prp(u, s, d);
        if(r < s || d < l) return;
        if(l <= s && d <= r) {
            LZ[u] ^= 1;
            prp(u, s, d);
            return;
        }
        update(l, r, u * 2, s, (s + d) / 2);
        update(l, r, u * 2 + 1, (s + d) / 2 + 1, d);
        V[u] = V[u * 2] + V[u * 2 + 1];
    }
}
vector<pair<int, int>> OP[MN];
ll acopera(int l) {
    if(l == n) return LLONG_MAX;
    ///c0 = 1 daca coloram primul patrat
    AINT::clear();
    for(int i = 1 + l; i <= n; i += 2 * l)
        AINT::update(i, i + l - 1);
    ll re = 0;
    for(int i = 1; i <= n; ++i) {
        for(auto [l, r] : OP[i])
            AINT::update(l, r);
        re += AINT::V[1];
        if(i % l == 0)
            AINT::update(1, n);
    }
    return re;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n >> k;
    ll re = LLONG_MAX;
    for (int i = 1, a, b, c, d; i <= k; ++i) {
        cin >> a >> b >> c >> d;
        OP[a].emplace_back(b, d);
        OP[c + 1].emplace_back(b, d);
    }
    vector<int> D{1};
    for (int i = 2; i * i <= n; ++i)
        if (i * i == n) D.push_back(i);
        else if (n % i == 0)
            D.push_back(i), D.push_back(n / i);
    for (auto it: D) {
        ll v = acopera(it);
        re = min(re, min(v, 1ll * n * n - v));
    }
    cout << re << "\n";
    return 0;
}

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