Submission #1134968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134968		12345678	Chessboard (IZhO18_chessboard)	C++20	100 / 100	638 ms	12356 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

ll n, k, a[nx], b[nx], c[nx], d[nx], st, l, ans=1e18, cnta, cntb, wa, ba, wb, bb;
vector<ll> add[nx], rem[nx];

ll cal(ll l, ll r, ll t)
{
    ll b=0;
    int cl=((l-1)/t)%2;
    ll nl=(((l-1)/t)+1)*t+1;
    if (r<nl)
    {
        if (cl) b=r-l+1;
        return b; 
    }
    if (cl) b=nl-l;
    l=nl;
    //cout<<"here "<<b<<' '<<l<<' '<<r<<'\n';
    int cr=((r-1)/t)%2;
    ll nr=(r-1)/t*t;
    if (cr) b+=r-nr;
    r=nr;
    if (r<l) return b;
    cl=((l-1)/t)%2;
    if ((((r-l+1)/t)%2)==0) b+=(r-l+1)/2;
    else b+=(r-l+1)/t/2*t+cl*t;
    return b;

}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=k; i++) cin>>a[i]>>b[i]>>c[i]>>d[i], add[a[i]].push_back(i), rem[c[i]+1].push_back(i);
    for (int t=1; t<n; t++)
    {
        if ((n%t)!=0) continue;
        cnta=cntb=wa=ba=wb=bb=0;
        for (int i=1; i<=n; i++)
        {
            l=(((i-1)/t)%2);
            if ((i-1)==(i-1)/t*t) swap(wa, ba);
            for (auto idx:add[i])
            {
                ll sz=d[idx]-b[idx]+1;
                auto x=cal(b[idx], d[idx], t);
                //cout<<"x "<<x<<' '<<sz<<'\n';
                if (l) x=sz-x;
                wa+=(sz-x);
                ba+=x;
            }
            for (auto idx:rem[i])
            {
                ll sz=d[idx]-b[idx]+1;
                auto x=cal(b[idx], d[idx], t);
                if (l) x=sz-x;
                wa-=(sz-x);
                ba-=x;
            }
            if ((n/t)%2==0) cnta+=n/2;
            else cnta+=(n/t)/2*t+l*t;
            //cout<<"debug "<<t<<' '<<i<<' '<<l<<' '<<wa<<' '<<ba<<'\n';
            cnta+=wa;
            cnta-=ba;
            l^=1;
            if ((i-1)==(i-1)/t*t) swap(wb, bb);
            for (auto idx:add[i])
            {
                ll sz=d[idx]-b[idx]+1;
                auto x=cal(b[idx], d[idx], t);
                if (l) x=sz-x;
                wb+=(sz-x);
                bb+=x;
            }
            for (auto idx:rem[i])
            {
                ll sz=d[idx]-b[idx]+1;
                auto x=cal(b[idx], d[idx], t);
                if (l) x=sz-x;
                wb-=(sz-x);
                bb-=x;
            }
            if ((n/t)%2==0) cntb+=n/2;
            else cntb+=(n/t)/2*t+l*t;
            cntb+=wb;
            cntb-=bb;
        }
        //cout<<"t "<<t<<' '<<cnta<<' '<<cntb<<'\n';
        ans=min({ans, cnta, cntb});
    }
    cout<<ans;
}

/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
*/

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