Submission #154286

#	Time	Username	Problem	Language	Result	Execution time	Memory
154286		dandrozavr	Chessboard (IZhO18_chessboard)	C++14	70 / 100	1224 ms	18592 KiB

chessboard

/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /◐/   /▐/   /▌/ /▀/ /░/ /🔥/   choose  own style!

***IT'S OUR LONG WAY TO THE OIILLLL***

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/


//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>
using namespace std;



#define pb push_back
#define ll long long
#define ld long doubl
#define fi first
#define se second
#define eb emplace_back
#define pii pair < int , int >
#define pipii pair< int, pair < int , int > >
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

//#include <ext/pb_ds/detail/standard_policies.hpp>'
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
namespace fastio {template <class T> ostream &operator<<(ostream &os, const vector<T> &container){for (auto &u : container)os << u << " ";return os;}template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) { return os << p.first << " " << p.second; }template <class T> ostream &operator<<(ostream &os, set<T> const& con) { for (auto &u : con) os << u << " "; return os; }void pr() {}template <typename T, typename... args> void pr(T x, args... tail) { cout << x << " "; pr(tail...);}}using namespace fastio;

const int N = 3e5 + 5;
const int MA = 1e6 + 1;

const int X[4] = {0, 0, 1, -1};
const int Y[4] = {-1, 1, 0, 0};

vector < int > g[N];
ll n, k;
vector < pair < pii , pii > >  q(N);
int x1, yy1, x2, y2;
int kk[4];

void update(pair < pii , pii > q, int len)
{
    x1 = q.fi.fi;
    x2 = q.se.fi;
    yy1 = q.fi.se;
    y2 = q.se.se;

    kk[0] = x1 % len;
    if (kk[0])
        kk[0] = len - kk[0];
    kk[0] = min(kk[0], x2 - x1 + 1);

    kk[1] = (x2 + 1) % len;
    kk[1] = min(kk[1], x2 - x1 + 1);

    kk[2] = yy1 % len;
    if (kk[2])
        kk[2] = len - kk[2];
    kk[2] = min(kk[2], y2 - yy1 + 1);

    kk[3] = (y2 + 1) % len;
    kk[3] = min(kk[3], y2 - yy1 + 1);
}


ll solve(int len)
{
    ll all = n * n;
    ll ans = 0;
    int llen = len * 2;

    vector < pair < pii , pii > >  z = q;

    for (int i = 0; i < n; ++i)
        if (i % llen < len)
            ans += (n / len / 2 + (n / len) % 2) * 1ll * len; else
            ans += (n / len / 2) * 1ll * len;
    for (int i = 0; i < k; ++i)
    {
        //kk[4]
        update(q[i], len);
//        cout<<ans<<endl;

        if (kk[2])
        {
            ll otv = 0;
            if (((x1 % llen < len) + (yy1 % llen < len)) % 2 == 0)
                otv -= kk[0]; else otv += kk[0];
            if (((x1 / len) != (x2 / len)) || (!kk[0]))
            if (((x2 % llen < len) + (yy1 % llen < len)) % 2 == 0)
                otv -= kk[1]; else otv += kk[1];

            ll dis = x2 - x1 + 1 - kk[0] - kk[1];
            ll bx = dis / len / 2 + (dis / len) % 2;
            ll mx = dis / len / 2;

            if ((1 + (yy1 % llen < len)) % 2 == 0)
               otv -= len * bx,
               otv += len * mx; else
               otv += len * bx,
               otv -= len * mx;
            ans += otv * kk[2];
            q[i].fi.se += kk[2];
        }

        if (q[i].fi.fi > q[i].se.fi || q[i].fi.se > q[i].se.se) continue;
        update(q[i], len);

        if (kk[0])
        {
            ll otv = 0;
            if (((x1 % llen < len) + (y2 % llen < len)) % 2 == 0)
                otv -= kk[3]; else otv += kk[3];
            ll dis = y2 - yy1 + 1 - kk[3];
            ll bx = dis / len / 2 + (dis / len) % 2;
            ll mx = dis / len / 2;
            if (((x1 % llen < len) + (yy1 % llen < len)) % 2 == 0)
               otv -= len * bx,
               otv += len * mx; else
               otv += len * bx,
               otv -= len * mx;
            ans += otv * kk[0];
            q[i].fi.fi += kk[0];
        }

        if (q[i].fi.fi > q[i].se.fi || q[i].fi.se > q[i].se.se) continue;
        update(q[i], len);

        if (kk[3])
        {
            ll otv = 0;
            if (((x2 % llen < len) + (y2 % llen < len)) % 2 == 0)
                otv -= kk[1]; else otv += kk[1];
            ll dis = x2 - x1 + 1 - kk[1];
            ll bx = dis / len / 2 + (dis / len) % 2;
            ll mx = dis / len / 2;
            if (((x1 % llen < len) + (y2 % llen < len)) % 2 == 0)
               otv -= len * bx,
               otv += len * mx; else
               otv += len * bx,
               otv -= len * mx;
            ans += otv * kk[3];
            q[i].se.se -= kk[3];
        }

        if (q[i].fi.fi > q[i].se.fi || q[i].fi.se > q[i].se.se) continue;
        update(q[i], len);
//        cout<<kk[0]<<" "<<kk[1]<<" "<<kk[2]<<" "<<kk[3]<<endl;
        if (kk[1])
        {
            ll otv = 0;
            ll dis = y2 - yy1 + 1;
            ll bx = dis / len / 2 + (dis / len) % 2;
            ll mx = dis / len / 2;
            if (((x2 % llen < len) + (yy1 % llen < len)) % 2 == 0)
               otv -= len * bx,
               otv += len * mx; else
               otv += len * bx,
               otv -= len * mx;
//            cout<<otv<<endl;
            ans += otv * kk[1];
            q[i].se.fi -= kk[1];
        }

        if (q[i].fi.fi > q[i].se.fi || q[i].fi.se > q[i].se.se) continue;
        update(q[i], len);

        //right
        ll dx = q[i].se.fi - q[i].fi.fi + 1;
        ll dy = q[i].se.se - q[i].fi.se + 1;
        ll by = dy / len / 2 + (dy / len) % 2;
        ll my = dy / len / 2;
        ll bx = dx / len / 2 + (dx / len) % 2;
        ll mx = dx / len / 2;
        ll alll = dx * dy;
        int nac = (q[i].fi.fi % llen < len) + (q[i].fi.se % llen < len);
//        cout<<len<<" "<<nac<<" "<<dx<<" "<<dy<<" "<<mx<<" "<<my<<" "<<bx<<" "<<by<<" "<<ans<<endl;

        if (nac % 2 == 0)
        {
            ll ch = (bx * by + mx * my) * 1ll * len * len;
            ans -= ch;
            ans += (alll - ch);
        } else
        {
            ll ch = (mx * by + bx * my) * 1ll * len * len;
            ans -= ch;
            ans += (alll - ch);
        }
    }
//    cout<<ans<<endl;
//    cout<<all<<endl;
//    cout<<endl;
    q = z;
    return min(ans, all - ans);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Estb_probitie
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    cin >> n >> k;

    for (int i = 0; i < k; ++i)
    {
        int x1, x2, yy1, y2;
        cin >> x1 >> yy1 >> x2 >> y2;
        --x1, --x2, --yy1, --y2;
        q[i] = {{x1, yy1}, {x2, y2}};
    }
    ll ans = solve(1);
    for (int i = 2; i * i <= n; ++i)
    if (n % i == 0)
        {
            ans = min(ans, solve(i));
            ans = min(ans, solve(n / i));
        }

    cout << ans;

}

Compilation message (stderr)

chessboard.cpp: In function 'long long int solve(int)':
chessboard.cpp:113:16: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
             if (((x1 / len) != (x2 / len)) || (!kk[0]))
                ^

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