Submission #521863

#	Time	Username	Problem	Language	Result	Execution time	Memory
521863		vonatlus	Chessboard (IZhO18_chessboard)	C++17	100 / 100	1184 ms	2724 KiB

chessboard

/// adil sultanov | vonat1us 

#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:36777216")

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
#define all(z) (z).begin(), (z).end()
 
using namespace std;

using ll = long long;
using pii = pair<int, int>;                                   

const int MOD = 1e9 + 7; 
const int INF = 1e9 + 1e2;
  
void fin() {
#ifdef AM
    freopen(".in", "r", stdin);
#endif        
}                   

const bool flag = 0;

const int N = 1e5+10;

void ma1n() {
    ll n, k;
    cin >> n >> k;
    vector<ll> v;
    for (ll i = 1; i <= sqrt(n); ++i) {
        if (n%i == 0) {
            v.pb(i);
            if (i*i != n) {
                v.pb(n/i);
            }
        }
    }
    sort(all(v));
    v.pop_back();
    vector<ll> res1(sz(v)), res2(sz(v));
    for (ll i = 0; i < sz(v); ++i) {
        ll d = v[i];
        ll cnt = n/d;
        ll cnt1 = cnt/2;
        ll cnt2 = (cnt+1)/2;
        res1[i] = cnt1*cnt2*d*d*2;
        res2[i] = n*n - res1[i];
    }
    
    auto get = [&](ll x, ll y, ll d) {
        if (x < 0 || y < 0) return 0ll;
        bool color = ((x/d)%2 != (y/d)%2); 
        ll cx = (x+1)%d;
        if (cx == 0) cx = d;
        ll cy = (y+1)%d;
        if (cy == 0) cy = d;
        ll res = 0;
        ll cur = (x/d)/2*d*cy;
        if (!color && (x/d)&1) {
            cur += d*cy;
        } 
        res += cur;
        if (color) { // black
            res += cx*cy;
        } 
        cur = (y/d)/2*d*cx;
        if (!color && (y/d)&1) {
            cur += d*cx;
        }
        res += cur;
        x = (x/d-1)*d+d-1;
        y = (y/d-1)*d+d-1;
        res += ((((x+1)/d)*((y+1)/d))/2)*d*d; 
        return res;
    };

    //cout << get(2, 2, 1) << " " << get(2, 1, 1) << " " << get(1, 2, 1) << " " << get(1, 1, 1) << "\n";
   // cout << get(2, 3, 2) << " " << get(2, 2, 2) << " " << get(1, 3, 2) << " " << get(1, 2, 2) << "\n";
    //return;

    while (k--) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--, c--, d--;    
        for (ll t = 0; t < sz(v); ++t) {
            ll dv = v[t];
            ll sum = get(c, d, dv) - get(c, b-1, dv) - get(a-1, d, dv) + get(a-1, b-1, dv);
            ll inv = (c-a+1)*1ll*(d-b+1) - sum;
            //cout << "D: " << dv << ", " << a << " " << b << " " << c << " " << d << " | " << sum << " " << inv << "\n";
            res1[t] -= sum;
            res1[t] += inv;
            res2[t] -= inv;
            res2[t] += sum;
        }
    }
    ll ans = n*n;
    for (ll i = 0; i < sz(v); ++i) {
        ans = min({ans, res1[i], res2[i]});    
    }
    cout << ans;
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr), fin();
    int ts = 1;
    if (flag) {
        cin >> ts;
    }
    while (ts--) {
        ma1n(); 
    }
    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