Submission #93194

#	Time	Username	Problem	Language	Result	Execution time	Memory
93194		antimirage	Chessboard (IZhO18_chessboard)	C++14	100 / 100	911 ms	3156 KiB

chessboard

#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()
 
using namespace std;

const int N = 1e5 + 5;

int m, x1[N], yy1[N], x2[N], y2[N];

long long n, ans = 1e18;

long long compute (int j1, int j2, long long bl)
{
	if (j1 / bl == j2 / bl)
	{
		if (j1 / bl & 1)
			return (j2 - j1 + 1);
		
		return 0ll;
	}
	long long res = 0;
	
	if (j1 / bl & 1)
		res += (j1 / bl * bl + bl - j1);
	
	j1 = j1 / bl * bl + bl;
	
	if (j2 / bl & 1)
		res += (j2 % bl + 1);
		
	j2 = j2 / bl * bl - 1;
	
	long long cn = (j2 / bl - j1 / bl + 1) / 2;
	
	if ( ((j2 / bl - j1 / bl + 1) & 1) && (j2 / bl & 1) )
		cn++;
	
	res += cn * bl;
	return res;
}

long long get (int i1, int j1, int i2, int j2, long long bl)
{
	long long res = 0, cn1 = compute( j1, j2, bl ), cn2 = (j2 - j1 + 1) - cn1;
	
	if (i1 / bl == i2 / bl)
	{
		if (i1 / bl & 1)
			res += cn1 * (i2 - i1 + 1);
		else
			res += cn2 * (i2 - i1 + 1);
	}
	else
	{
		if (i1 / bl & 1)
			res += cn1 * (i1 / bl * bl + bl - i1);
		else
			res += cn2 * (i1 / bl * bl + bl - i1);
			
		i1 = i1 / bl * bl + bl;
		
		if (i2 / bl & 1)
			res += cn1 * (i2 % bl + 1);
		else
			res += cn2 * (i2 % bl + 1);
			
		i2 = i2 / bl * bl - 1;
		
		long long cn = (i2 / bl - i1 / bl + 1) / 2;
		
		if ( (i2 / bl - i1 / bl + 1) & 1 )
		{
			if ( i1 / bl % 2 == 0 )
			{
				res += (cn + 1) * cn2 * bl;
				res += cn * cn1 * bl;
			}
			else
			{
				res += (cn + 1) * cn1 * bl;
				res += cn * cn2 * bl;
			}
		}
		else
		{
			res += cn * cn1 * bl;
			res += cn * cn2 * bl;
		}
	}
	return res;
}

void calc (long long x)
{
	long long res = get(0, 0, n - 1, n - 1, x) ;
	
	for (int i = 1; i <= m; i++)
	{
		long long sup = get( x1[i], yy1[i], x2[i], y2[i], x);
		res -= sup;
		res += ( (x2[i] - x1[i] + 1) * 1ll * (y2[i] - yy1[i] + 1) - sup);
	}
	ans = min(ans, res);
	ans = min(ans, n * n - res);
}

main() 
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d %d %d", &x1[i], &yy1[i], &x2[i], &y2[i]);
		x1[i]--;
		yy1[i]--;
		x2[i]--;
		y2[i]--;
	}
	for (long long i = 1; i * i <= n; i++)
	{
		if ( n % i != 0 ) continue;
		calc(i);
		if (n / i != n)
			calc(n / i);
	}
	cout << ans << endl;
}
/**
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
**/

Compilation message (stderr)

chessboard.cpp:112:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() 
      ^
chessboard.cpp: In function 'int main()':
chessboard.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &x1[i], &yy1[i], &x2[i], &y2[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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