Submission #347003

#	Time	Username	Problem	Language	Result	Execution time	Memory
347003		andrii	Chessboard (IZhO18_chessboard)	C++17	70 / 100	974 ms	13164 KiB

chessboard

// -- //
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define pll pair<ll, ll>
#define ppll pair<pll, pll>
#define x first
#define y second
using namespace std;
typedef long long rll;
typedef int ll;
const ll N = 1e5+228;
ppll a[N];
vector<pll> add[N], del[N];
ll n, k;
rll res;
inline void ch(ll m, ll bln) __attribute__((always_inline));
inline void ch(ll m, ll bln){
    rll bob=0, bow=0;
    rll no[2]={0};
    for(ll i = 1;i<=n;i++){
        for(auto &j : add[i]){
            ll s = j.x, e = j.y;
            --s, e--;
            ll bs = s/m, be = e/m;
            rll bse = ((rll)bs+1)*m-1;
            if(bs==be) no[bs&1] += e-s+1;
            else if(bs+1==be){
                no[bs&1] += bse-s+1;
                no[be&1] += e-bse;
            }else{
                no[bs&1] += bse-s+1;
                no[be&1] += e-bse;
                bs++, be--;
                ll kb = (be-bs+1)/2;
                no[bs&1] += ((rll)(be-bs+1-kb))*m;
                no[be&1] += ((rll)kb)*m;
            }
        }
        if(((i-1)/m)&1){
            bow+=no[0], bob+=no[1];
        }else{
            bob+=no[0], bow+=no[1];
        }
        for(auto &j : del[i]){
            ll s = j.x, e = j.y;
            --s, e--;
            ll bs = s/m, be = e/m;
            rll bse = ((rll)bs+1)*m-1;
            if(bs==be) no[bs&1] -= e-s+1;
            else if(bs+1==be){
                no[bs&1] -= bse-s+1;
                no[be&1] -= e-bse;
            }else{
                no[bs&1] -= bse-s+1;
                no[be&1] -= e-bse;
                bs++, be--;
                ll kb = (be-bs+1)/2;
                no[bs&1] -= ((rll)(be-bs+1-kb))*m;
                no[be&1] -= ((rll)kb)*m;
            }
        }
    }
    rll mbb = 1LL*((rll)(bln>>1))*((rll)m)*((rll)n)+1LL*((rll)((bln&1) ? (bln+1)>>1 : 0))*((rll)m)*((rll)m);
    rll v1 = (mbb-bob)+bow;
    rll v2 = bob+(((rll)n*n)-mbb-bow);
    if(v1<res) res=v1;
    if(v2<res) res=v2;
}
signed main(){
	cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for(ll i =0 ;i<k;i++){
        cin >> a[i].x.x >> a[i].x.y >> a[i].y.x >> a[i].y.y;
        add[a[i].x.y].push_back({a[i].x.x, a[i].y.x});
        del[a[i].y.y].push_back({a[i].x.x, a[i].y.x});
    }
    res=(rll)n*n;
    for(ll i = 1;i*i<=n;i++){
        ll k = n/i;
        if(n-k*i) continue;
        ch(i, k);
        if(i>1) ch(k, i);
    }
    cout<<res;
}

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