Submission #523557

#	Time	Username	Problem	Language	Result	Execution time	Memory
523557		RaresFelix	Chessboard (IZhO18_chessboard)	C++17	47 / 100	2027 ms	11172 KiB

chessboard

#include <bits/stdc++.h>

#define MN 107171
using ll = long long;
using namespace std;
int n, k;
tuple<int, int, int, int> R[MN];

namespace AINT {
    int V[4 * MN], LZ[4 * MN];
    void clear(int u = 1, int s = 1, 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);
    }
    void prp(int u, int s, 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(int l, 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, int c0) {
    if(l == n) return LLONG_MAX;
    ///c0 = 1 daca coloram primul patrat
    AINT::clear();
    for(int i = 1 + (1 - c0) * 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;
        R[i] = make_tuple(a, b, c, d);
        OP[a].emplace_back(b, d);
        OP[c + 1].emplace_back(b, d);
    }
    vector<int> D;
    for (int i = 1; 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)
        re = min(re, min(acopera(it, 0), acopera(it, 1)));
    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