Submission #652635

#	Time	Username	Problem	Language	Result	Execution time	Memory
652635		ymm	Chessboard (IZhO18_chessboard)	C++17	100 / 100	337 ms	5824 KiB

chessboard

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

vector<ll> divs(ll x)
{
	vector<ll> ans;
	for (ll y = 1; y*y <= x; ++y) {
		if (x%y == 0) {
			ans.push_back(y);
			ans.push_back(x/y);
		}
	}
	return ans;
}

pll get(ll l, ll r, ll len)
{
	ll len2 = len*2;
	ll l2 = l%len2? l-l%len2+len2: l;
	ll r2 = r%len2? r-r%len2: r;
	ll a0 = (r2-l2)/2;
	ll a1 = (r2-l2)/2;
	a0 += max(0ll, l2-l-len);
	a1 += min(len, l2-l);
	a0 += min(len, r-r2);
	a1 += max(0ll, r-r2-len);
	return {a0, a1};
}

const int N = 100'010;
ll l0[N], r0[N];
ll l1[N], r1[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	ll n, k;
	cin >> n >> k;
	Loop (i,0,k) {
		cin >> l0[i] >> l1[i];
		cin >> r0[i] >> r1[i];
		--l0[i]; --l1[i];
	}
	ll ans = n*n;
	for (ll x : divs(n)) {
		if (x == n)
			continue;
		ll sm0 = ((n/x) * (n/x) + 1)/2 * x * x;
		ll sm1 = ((n/x) * (n/x))/2 * x * x;
		Loop (i,0,k) {
			auto [a0, a1] = get(l0[i], r0[i], x);
			auto [b0, b1] = get(l1[i], r1[i], x);
			ll bl0 = a0*b0 + a1*b1;
			ll bl1 = a0*b1 + a1*b0;
			sm0 -= bl0;
			sm1 -= bl1;
			sm0 += (r0[i] - l0[i]) * (r1[i] - l1[i]) - bl0;
			sm1 += (r0[i] - l0[i]) * (r1[i] - l1[i]) - bl1;
		}
		ans = min(ans, sm0);
		ans = min(ans, sm1);
	}
	cout << ans << '\n';
}

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