Submission #287373

#	Time	Username	Problem	Language	Result	Execution time	Memory
287373		Berted	Chessboard (IZhO18_chessboard)	C++14	100 / 100	575 ms	10524 KiB

chessboard

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define pii pair<ll, ll>
#define fst first
#define snd second

const ll INF = 1e12;

using namespace std;

struct data
{
	ll x, y1, y2; bool t;
	inline bool operator<(const data& r) const
	{
		return make_pair(make_pair(x, y1), make_pair(y2, t)) < make_pair(make_pair(r.x, r.y1), make_pair(r.y2, r.t));
	}
};

int N, K;
ll S, p1, p2, ans = INF;
vector<data> A;

inline void a1(ll Y1, ll Y2, ll v)
{
	ll R = Y2 / (2 * S), L = Y1 / (2 * S), a = 0;
	if (L == R) {a += max(0LL, min(Y2 + 1, 2 * L * S + S) - Y1); }
	else
	{
		a += (R - L - 1) * S;
		a += max(0LL, 2 * L * S + S - Y1);
		a += min(Y2 + 1, 2 * R * S + S) - 2 * R * S;
	}
	p1 += a * v;
}

inline void a2(ll Y1, ll Y2, ll v)
{
	ll R = Y2 / (2 * S), L = Y1 / (2 * S), a = 0;
	if (L == R) {a += max(0LL, Y2 + 1 - max(Y1, 2 * L * S + S)); }
	else
	{
		a += (R - L - 1) * S;
		a += 2 * (L + 1) * S - max(Y1, 2 * L * S + S);
		a += max(0LL, Y2 + 1 - 2 * R * S - S);
	}
	p2 += a * v;
}

void solve()
{
	p1 = 0; p2 = 0;
	ll s1 = 0, s2 = 0, t1 = 0, t2 = 0; int j = 0;
	for (int i = 0; i < N; i++)
	{
		for (; j < A.size() && A[j].x <= i; j++)
		{
			if (A[j].t) 
			{
				a1(A[j].y1, A[j].y2, -1);
				a2(A[j].y1, A[j].y2, -1);
			}
			else
			{
				a1(A[j].y1, A[j].y2, 1);
				a2(A[j].y1, A[j].y2, 1);
			}
		}
		t1 += p1; t2 += p2;
		if ((i + 1) % S == 0)
		{
			ll c = (N / S + 1) / 2, f = (N / S) / 2; c *= S * S; f *= S * S;
			if (i / S % 2 == 0)
			{
				s1 += (c - t1) + t2;
				s2 += t1 + (f - t2); 
			}
			else
			{
				s2 += (c - t1) + t2;
				s1 += t1 + (f - t2); 
			}
			t1 = 0; t2 = 0;
		}
	}
	ans = min(ans, min(s1, s2));
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> K;
	for (int i = 0; i < K; i++)
	{
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		data a; a.x = x1 - 1; a.y1 = y1 - 1; a.y2 = y2 - 1; a.t = 0;
		data b; b.x = x2; b.y1 = y1 - 1; b.y2 = y2 - 1; b.t = 1;
		A.push_back(a); A.push_back(b);
	}
	sort(A.begin(), A.end());
	for (int i = 1; i * i <= N; i++)
	{
		if (N % i == 0)
		{
			S = i; solve();
			if (i * i < N && i > 1) {S = N / i; solve();}
		}
	}
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'void solve()':
chessboard.cpp:58:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (; j < A.size() && A[j].x <= i; j++)
      |          ~~^~~~~~~~~~

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