Submission #572514

#	Time	Username	Problem	Language	Result	Execution time	Memory
572514		vovamr	Chessboard (IZhO18_chessboard)	C++17	100 / 100	400 ms	4180 KiB

chessboard

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

inline void solve() {
	int n, m;
	cin >> n >> m;
	ve<pair<pii,pii>> a(m);
	for (auto &[a1, a2] : a) {
		auto &[x1, y1] = a1;
		auto &[x2, y2] = a2;
		cin >> x1 >> y1 >> x2 >> y2;
		--x1, --y1, --x2, --y2;
	}

	auto even = [](ll l, ll r) { if (l > r) {return 0ll;} return r / 2 - (l + 1) / 2 + 1; };
	auto odd = [&even](ll l, ll r) { if (l > r) {return 0ll;} return r - l + 1 - even(l, r); };

	auto run = [&](ll d) {

		ll ans1 = 0, ans2 = 0;
		for (auto &[a1, a2] : a) {
			auto &[x1, y1] = a1;
			auto &[x2, y2] = a2;

			ll evx, odx, evy, ody;
			{
				ll mn = x1 / d, mx = x2 / d;
				if (mn == mx) {
					if (mn & 1) evx = 0, odx = x2 - x1 + 1;
					else odx = 0, evx = x2 - x1 + 1;
				}
				else {
					evx = odx = 0;
					evx += d * even(mn + 1, mx - 1);
					odx += d * odd(mn + 1, mx - 1);
					
					if (mn & 1) odx += (mn + 1) * d - x1;
					if (mx & 1) odx += x2 - mx * d + 1;

					if (mn & 1 ^ 1) evx += (mn + 1) * d - x1;
					if (mx & 1 ^ 1) evx += x2 - mx * d + 1;
				}
			}
			{
				ll mn = y1 / d, mx = y2 / d;
				if (mn == mx) {
					if (mn & 1) evy = 0, ody = y2 - y1 + 1;
					else ody = 0, evy = y2 - y1 + 1;
				}
				else {
					evy = ody = 0;
					evy += d * even(mn + 1, mx - 1);
					ody += d * odd(mn + 1, mx - 1);
					
					if (mn & 1) ody += (mn + 1) * d - y1;
					if (mx & 1) ody += y2 - mx * d + 1;

					if (mn & 1 ^ 1) evy += (mn + 1) * d - y1;
					if (mx & 1 ^ 1) evy += y2 - mx * d + 1;
				}
			}

			// corner is white
			ans1 += evx * evy + odx * ody;
			ans1 -= (evx * ody + evy * odx);

			// corner is black
			ans2 += evx * ody + evy * odx;
			ans2 -= (evx * evy + odx * ody);
		}
		ll e = even(1, n / d), o = odd(1, n / d);
		ans1 += d * d * (e * o + o * e);
		ans2 += d * d * (e * e + o * o);
		return min(ans1, ans2);
	};

	ll res = inf;
	for (int d = 1; d * d <= n; ++d) {
		if (n % d) continue;
		chmin(res, run(d));
		if (d * d != n && d > 1) chmin(res, run(n / d));
	}
	cout << res;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message (stderr)

chessboard.cpp: In lambda function:
chessboard.cpp:59:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   59 |      if (mn & 1 ^ 1) evx += (mn + 1) * d - x1;
      |          ~~~^~~
chessboard.cpp:60:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   60 |      if (mx & 1 ^ 1) evx += x2 - mx * d + 1;
      |          ~~~^~~
chessboard.cpp:77:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   77 |      if (mn & 1 ^ 1) evy += (mn + 1) * d - y1;
      |          ~~~^~~
chessboard.cpp:78:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   78 |      if (mx & 1 ^ 1) evy += y2 - mx * d + 1;
      |          ~~~^~~

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