#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 ++){
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 += ((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;
}
}
}
}
}
return cnt_move;
}
int main(){
ll n, m;
cin >> n >> m;
for(int i = 1; i <= m; i ++){
cin >> 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 << abs(ans);
}
/*
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
chessboard.cpp: In function 'int main()':
chessboard.cpp:281:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
281 | for(int i = 0; i < divv.size(); i ++){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
308 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
300 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
3628 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
3628 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
308 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
300 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Execution timed out |
2045 ms |
3628 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
