Submission #155167

#	Time	Username	Problem	Language	Result	Execution time	Memory
155167		srvlt	Chessboard (IZhO18_chessboard)	C++14	8 / 100	42 ms	4472 KiB

chessboard

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse2,avx")
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
//#define int long long
using namespace std;

void dout() {
    cerr << endl;
}

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 3;
const ll inf = 1e18;

int k, p[2][N], rx[N], ry[N], rx2[N], ry2[N], pre1[N], pre2[N];
ll n, ans = inf, A, Z, S, W, sq[N];

int color(int x, int y) {
    return ((x - 1) / A + (y - 1) / A + Z) & 1;
}

int num(int x) {
    return (x - 1) / A & 1;
}

ll getL() {
    int x = n / A;
    ll res = sq[A] * (sq[pre1[x]] + sq[pre2[x]]);
    if (Z == 0) {
        return res;
    }   else {
        return sq[n] - res;
    }
}

ll getval(int l, int r, int a, int b) {
    ll res1 = 0;
    if (l >= 1) {
        int q = (l - 1) / A;
        int last = q * A + 1;
        if (num(last) == 0) {
            res1 += (l - last + 1) * a;
        }   else {
            res1 += (l - last + 1) * b;
        }
        res1 += (pre1[q] * a + pre2[q] * b) * A;
    }

    ll res2 = 0;
    if (l >= 1) {
        int q = (r - 1) / A;
        int last = q * A + 1;
        if (num(last) == 0) {
            res2 += (r - last + 1) * a;
        }   else {
            res2 += (r - last + 1) * b;
        }
        res2 += (pre1[q] * a + pre2[q] * b) * A;
    }
    return res2 - res1;
}

ll getans() {
    for (int i = 1; i <= n; i++) {
        p[0][i] = p[0][i - 1];
        p[1][i] = p[1][i - 1];
        if (color(i, 1)) {
            p[0][i]++;
        }   else {
            p[1][i]++;
        }
    }
    ll res = 0;
    for (int i = 0; i < k; i++) {
        int v1 = p[0][rx2[i]] - p[0][rx[i] - 1];
        int v2 = p[1][rx2[i]] - p[1][rx[i] - 1];
        res += getval(ry[i] - 1, ry2[i], v1, v2);
    }
    return res;
}

void solve(int tc) {
    cin >> n >> k;
    for (int i = 0; i <= n + 1; i++) {
        pre1[i] = ((i + 1) >> 1);
        pre2[i] = (i >> 1);
        sq[i] = (ll)i * i;
    }
    for (int i = 0; i < k; i++) {
        cin >> rx[i] >> ry[i] >> rx2[i] >> ry2[i];
        S += (ll)(rx2[i] - rx[i] + 1) * (ry2[i] - ry[i] + 1);
    }
    vector <int> factors = {};
    for (int i = 1; i < n; i++) {
        if (n % i == 0) {
            factors.pb(i);
        }
    }
    for (auto i : factors) {
        A = i;
        for (int j = 0; j < 2; j++) {
            Z = j;
            W = getans();
            ans = min(ans, W + W + getL() - S);
        }
    }
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}

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