#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>
#define ll long long int
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
ll inf2 = 3e18;
ll x1[ 100111 ], x2[ 100111 ];
ll y11[ 100111 ], y2[ 100111 ], ans = inf2;
vector < ll > divv;
map < ll , ll > mp;
ll white_first(ll sz, ll n, ll m){
ll sqrs = n / sz;
ll cnt_move = (sqrs & 1) ? ((((sqrs >> 1) * ((sqrs >> 1) + 1)) << 1) * (sz * sz)) : (sqrs >> 1) * (sqrs) * (sz * sz);
// cout << "w: " << cnt_move << " sz: " << sz << "\n";
for(int i = 1; i <= m; i ++){
if(x1[ i ] == x2[ i ] && y11[ i ] == y2[ i ]){
if(((x1[ i ] + sz - 1) / sz) & 1)
if(((y11[ i ] + sz - 1) / sz) & 1)
cnt_move ++;
else
cnt_move --;
else
if(((y11[ i ] + sz - 1) / sz) & 1)
cnt_move --;
else
cnt_move ++;
continue;
}
for(int j = 1, j2 = 1; j <= n; j += sz, j2 ++){
if(j <= x1[ i ] && x2[ i ] <= (j2 * sz)){
for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){
if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
break;
}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);
}else{
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
break;
}
}
}else if(j <= x1[ i ] && x1[ i ] <= (j2 * sz) && (j2 * sz) <= x2[ i ]){
for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){
if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
break;
}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);
}else{
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
break;
}
}
}else if(x1[ i ] <= j && (j2 * sz) <= x2[ i ]){
for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){
if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
break;
}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);
}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);
else
cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);
else
cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);
}else{
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
else
cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
else
cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
break;
}
}
}else{
for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){
if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
break;
}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);
}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);
else
cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);
else
cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);
}else{
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
else
cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
else
cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
break;
}
}
}
}
}
return cnt_move;
}
int main(){
ll n, m;
cin >> n >> m;
for(int i = 1; i <= m; i ++){
scanf("%lld%lld%lld%lld", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ])
}
divv.pb(1);
for(int i = 2; i <= ((ll)ceil(sqrt(n))); i ++){
if(n % i == 0 && !mp[ i ] && i != n){
divv.pb(i);
mp[ i ] ++;
if(!mp[ n / i ]){
divv.pb(n / i);
mp[ n / i ] ++;
}
}
}
// sort(all(divv));
for(int i = 0; i < divv.size(); i ++){
ll white = white_first(divv[ i ], n, m);
ans = min(ans, min((n * n) - white, white));
// cout << white << " " << (n * n) - white << "\n";
}
cout << ans;
}
Compilation message
chessboard.cpp: In function 'int main()':
chessboard.cpp:277:69: error: expected ';' before '}' token
277 | scanf("%lld%lld%lld%lld", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ])
| ^
| ;
278 | }
| ~
chessboard.cpp:294:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
294 | for(int i = 0; i < divv.size(); i ++){
| ~~^~~~~~~~~~~~~
chessboard.cpp:277:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
277 | scanf("%lld%lld%lld%lld", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ])
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
