제출 #155531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
155531		Dasha_Gnedko	Chessboard (IZhO18_chessboard)	C++14	100 / 100	1975 ms	2040 KiB

chessboard

#include <bits/stdc++.h>

//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define endl '\n'
//#define int long long

using namespace std;

//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 100;
const int M = 21890;
const ll mod = 1e9 + 7;
const ll MOD = 998244353;
const int P = 1336;
const ld eps = 0.000000001;
const int inf = 1e9 + 7;
const ll inff = 1e18 + 7;

mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

int l1[N], r1[N], l2[N], r2[N];
int m;
vector <int> a;

pair <int, pair <ll, ll> > get(ll r, ll x, ll y, int fl)
{
    ll gx = x / r, gy = y / r;
    if (x % r) gx++;
    if (y % r) gy++;

    bool f;

    if (fl == 0)
    {
        if (gx % 2)
        {
            if (gy % 2) f = 0;
            else f = 1;
        }
        else if (gy % 2) f = 1;
        else f = 0;
    }
    else
    {
        if (gx % 2)
        {
            if (gy % 2) f = 1;
            else f = 0;
        }
        else if (gy % 2) f = 0;
        else f = 1;
    }

    ll bx = 1ll * gx * r - x + 1;
    ll by = 1ll * gy * r - y + 1;

    return {f, {bx, by}};
}

ll solve(ll r, ll x1, ll y1, ll x2, ll y2, int fl)
{
    if (x1 > x2 || y1 > y2) return 0;

    ll gx1 = x1 / r + 1, gx2 = x2 / r;
    if (x1 % r != 1) gx1++;
    if (x1 % r == 0) gx1--;

    ll gy1 = y1 / r + 1, gy2 = y2 / r;
    if (y1 % r != 1) gy1++;
    if (y1 % r == 0) gy1--;

    if (r == 1)
    {
        gx1 = x1;
        gx2 = x2;
        gy1 = y1;
        gy2 = y2;
    }

    if (gx1 > gx2 || gy1 > gy2)
    {
        pair < int, pair <ll, ll> > p;

            ll gx = x1 / r, gy = y1 / r;
            if (x1 % r) gx++;
            if (y1 % r) gy++;

            bool f;

            if (fl == 0)
            {
                if (gx % 2)
                {
                    if (gy % 2) f = 0;
                    else f = 1;
                }
                else if (gy % 2) f = 1;
                else f = 0;
            }
            else
            {
                if (gx % 2)
                {
                    if (gy % 2) f = 1;
                    else f = 0;
                }
                else if (gy % 2) f = 0;
                else f = 1;
            }

            ll bx = 1ll * gx * r - x1 + 1;
            ll by = 1ll * gy * r - y1 + 1;

            p.F = f;
            p.S.F = bx;
            p.S.S = by;

        if (gx1 > gx2 && gy1 > gy2)
        {
            if (x1 + p.S.F > x2 && y1 + p.S.S > y2)
            {
                if (p.F == 0) return 1ll * (x2 - x1 + 1) * (y2 - y1 + 1);
                else return 0;
            }

            if (x1 + p.S.F > x2)
            {
                ll S = 1ll * (x2 - x1 + 1) * p.S.S;
                if (p.F == 0) return S;
                else return 1ll * (x2 - x1 + 1) * (y2 - y1 + 1) - S;
            }

            if (y1 + p.S.S > y2)
            {
                ll S = 1ll * (y2 - y1 + 1) * p.S.F;
                if (p.F == 0) return S;
                else return 1ll * (x2 - x1 + 1) * (y2 - y1 + 1) - S;
            }

            ll v1 = 1ll * p.S.F * p.S.S + 1ll * (x2 - x1 + 1 - p.S.F) * (y2 - y1 + 1 - p.S.S);
            ll v2 = 1ll * (x2 - x1 + 1) * (y2 - y1 + 1) - v1;

            if (p.F == 0) return v1;
            else return v2;

        }

        if (gx1 <= gx2)
        {

            if (y1 + p.S.S <= y2)
            {
                return 1ll * solve(r, x1, y1, x2, y1 + p.S.S - 1, fl) + solve(r, x1, y1 + p.S.S, x2, y2, fl);
            }

            ll S = 0;
            if (p.S.F < r) S += 1ll * p.S.F * (y2 - y1 + 1);
            ll k = (gx2 - gx1 + 1) / 2;
            if (p.S.F == r) k = (gx2 - gx1 + 1 + 1) / 2;
            S += 1ll * (y2 - y1 + 1) * r * k;

            pair < int, pair <ll, ll> > p1;

            gx = (gx2 * r + 1) / r; gy = y1 / r;
            if ((gx2 * r + 1) % r) gx++;
            if (y1 % r) gy++;

            if (fl == 0)
            {
                if (gx % 2)
                {
                    if (gy % 2) f = 0;
                    else f = 1;
                }
                else if (gy % 2) f = 1;
                else f = 0;
            }
            else
            {
                if (gx % 2)
                {
                    if (gy % 2) f = 1;
                    else f = 0;
                }
                else if (gy % 2) f = 0;
                else f = 1;
            }

            bx = 1ll * gx * r - (gx2 * r + 1) + 1;
            by = 1ll * gy * r - y1 + 1;

            p1.F = f;
            p1.S.F = bx;
            p1.S.S = by;

            if (p1.F == p.F && gx2 * r + 1 <= x2) S += 1ll * (x2 - gx2 * r) * (y2 - y1 + 1);

            if (p.F == 0) return S;
            else return 1ll * (x2 - x1 + 1) * (y2 - y1 + 1) - S;

        }

        if (gy1 <= gy2)
        {


            if (x1 + p.S.F <= x2)
            {
                return 1ll * solve(r, x1, y1, x1 + p.S.F - 1, y2, fl) + solve(r, x1 + p.S.F, y1, x2, y2, fl);
            }

            ll S = 0;
            if (p.S.S < r) S += 1ll * (x2 - x1 + 1) * p.S.S;
            ll k = (gy2 - gy1 + 1) / 2;
            if (p.S.S == r) k = (gy2 - gy1 + 1 + 1) / 2;
            S += 1ll * (x2 - x1 + 1) * r * k;

            pair < int, pair <ll, ll> > p1;

            gx = x1 / r; gy = (gy2 * r + 1) / r;
            if (x1 % r) gx++;
            if ((gy2 * r + 1) % r) gy++;

            if (fl == 0)
            {
                if (gx % 2)
                {
                    if (gy % 2) f = 0;
                    else f = 1;
                }
                else if (gy % 2) f = 1;
                else f = 0;
            }
            else
            {
                if (gx % 2)
                {
                    if (gy % 2) f = 1;
                    else f = 0;
                }
                else if (gy % 2) f = 0;
                else f = 1;
            }

            bx = 1ll * gx * r - x1 + 1;
            by = 1ll * gy * r - (gy2 * r + 1) + 1;

            p1.F = f;
            p1.S.F = bx;
            p1.S.S = by;

            if (p1.F == p.F && gy2 * r + 1 <= y2) S += (y2 - gy2 * r) * (x2 - x1 + 1);

            if (p.F == 0) return S;
            else return (x2 - x1 + 1) * (y2 - y1 + 1) - S;

        }

        return 0;

    }

    ll stx = 1ll * gx1 * r - r + 1;
    ll ex = 1ll * gx2 * r;

    ll sty = 1ll * gy1 * r - r + 1;
    ll ey = 1ll * gy2 * r;

    ll kolx = (gx2 - gx1 + 1 + 1) / 2;
    ll koly = (gy2 - gy1 + 1 + 1) / 2;

    ll S = 1ll * kolx * koly * r * r;

    kolx = (gx2 - gx1 + 1) / 2;
    koly = (gy2 - gy1 + 1) / 2;

    S += 1ll * kolx * koly * r * r;

    pair < int, pair <ll, ll> > p;

    ll gx = stx / r, gy = sty / r;
    if (stx % r) gx++;
    if (sty % r) gy++;

    bool f;

    if (fl == 0)
    {
        if (gx % 2)
        {
            if (gy % 2) f = 0;
            else f = 1;
        }
        else if (gy % 2) f = 1;
        else f = 0;
    }
    else
    {
        if (gx % 2)
        {
            if (gy % 2) f = 1;
            else f = 0;
        }
        else if (gy % 2) f = 0;
        else f = 1;
    }

    ll bx = 1ll * gx * r - stx + 1;
    ll by = 1ll * gy * r - sty + 1;

    p.F = f;
    p.S.F = bx;
    p.S.S = by;

    ll add = solve(r, x1, y1, stx - 1, y2, fl);
    add += solve(r, ex + 1, y1, x2, y2, fl);
    add += solve(r, stx, y1, ex, sty - 1, fl);
    add += solve(r, stx, ey + 1, ex, y2, fl);

    if (p.F == 0) return S + add;
    else return 1ll * (ex - stx + 1) * (ey - sty + 1) - S + add;
}


int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    ll n;
    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        cin >> l1[i] >> r1[i] >> l2[i] >> r2[i];
    }

    a.pb(1);

    int d = 2;
    while (d * d <= n)
    {
        if (n % d == 0)
        {
            a.pb(d);
            a.pb(n / d);
        }
        d++;
    }

    int kopn = n;
    ll ans = inff;

    for(auto to: a)
    {
        n = kopn;
        ll r = to;

        ll S = 1ll * n * n;
        n /= r;

        ll kx = 1ll * (n + 1) / 2;
        ll k1 = kx * kx;
        kx = 1ll * n / 2;
        k1 += kx * kx;
        k1 *= r * r;

        ll k2 = S - k1;

        ll v1 = 0, v2 = 0;

        for(int i = 0; i < m; i++)
        {
            ll pl = 1ll * (l2[i] - l1[i] + 1) * (r2[i] - r1[i] + 1);
            ll c1 = solve(r, l1[i], r1[i], l2[i], r2[i], 1);
            ll c2 = solve(r, l1[i], r1[i], l2[i], r2[i], 0);

            v1 += c1;
            k1 -= (pl - c1);

            v2 += c2;
            k2 -= (pl - c2);
        }

        ans = min(ans, min(v1 + k1, v2 + k2));
    }

    cout << ans;
}

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