/** - dwuy -
/> フ
| _ _|
/`ミ _x ノ
/ |
/ ヽ ?
/ ̄| | | |
| ( ̄ヽ__ヽ_)_)
\二つ
**/
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "IZhO18_chessboard"
#define int long long
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;
struct Rect{
int x, y, u, v;
void read(){
cin >> x >> y >> u >> v;
}
};
int n, k;
Rect a[MX];
namespace SUB134{
bool OK(){
return n <= 1000;
}
const int MS = 1005;
int r[MS][MS];
void solve(){
for(int i=1; i<=k; i++){
for(int x=a[i].x; x<=a[i].u; x++){
for(int y=a[i].y; y<=a[i].v; y++){
r[x][y] = 1;
}
}
}
int ans = 1e18;
for(int d=1; d<n; d++) if(n%d == 0){
int res = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
int w = ((i - 1)/d + (j - 1)/d)%2;
if(w) res += !r[i][j];
else res += r[i][j];
}
}
ans = min({ans, res, n*n - res});
}
cout << ans;
}
}
namespace SUB2{
bool OK(){
for(int i=2; i*i<=n; i++) if(n%i == 0) return 0;
for(int i=1; i<=k; i++) if(a[i].x != a[i].u || a[i].y != a[i].v) return 0;
return 1;
}
void solve(){
int res = n*(n/2) + n/2;
if(n == 2) res = 2;
for(int i=1; i<=k; i++){
int d = (a[i].x + a[i].y)%2;
if(d) res--;
else res++;
}
cout << min(res, n*n - res);
}
}
namespace FULL{
bool OK(){
return 1;
}
int w[MX];
int cnt(int x, int y, int u, int v, int mid){
int height = u - x + 1;
int width = v - y + 1;
int ans = height/(2 * mid) * mid * width;
height %= 2 * mid;
int layer1 = 0;
if((x - 1)/mid%2 == 0) layer1 = w[v] - w[y - 1];
else layer1 = (v - y + 1) - (w[v] - w[y - 1]);
int layer2 = width - layer1;
// cout << height << ' ' << layer1 << ' ' << layer2 << endl;
int thick = mid - (x - 1)%mid;
ans += min(thick, height) * layer1;
if(height > thick) ans += min(mid, height - thick) * layer2;
if(height > thick + mid) ans += layer1*(height - thick - mid);
return ans;
}
void solve(){
int ans = 1e18;
for(int u=1; u<n; u++) if(n%u == 0){
int d = n/u;
int cur = u*n*(d/2);
if(d&1) cur += u*u*(d/2);
for(int i=1; i<=n; i++){
w[i] = w[i-1];
if(((i - 1)/u)%2) w[i]++;
}
// cout << u << endl;
for(int i=1; i<=k; i++){
int delta = cnt(a[i].x, a[i].y, a[i].u, a[i].v, u);
// cout << delta << endl;
cur -= delta;
cur += (a[i].u - a[i].x + 1)*(a[i].v - a[i].y + 1) - delta;
}
// cout << cur << " == " << n*n - cur << endl << endl;
ans = min({ans, cur, n*n - cur});
}
cout << ans;
}
}
int32_t main(){
fastIO;
//file(TASK);
cin >> n >> k;
for(int i=1; i<=k; i++) a[i].read();
// if(SUB134::OK()) return SUB134::solve(), 0;
// if(SUB2::OK()) return SUB2::solve(), 0;
if(FULL::OK()) return FULL::solve(), 0;
// int mx = 0;
// for(int i=1; i<=1000; i++){
// int ans = 0;
// for(int j=1; j*j<=i; j++) if(i%j == 0){
// ans++;
// ans += j*j != i;
// }
// mx = max(mx, ans);
// }
// cerr << mx;
return 0;
}
/**
max numbers of divisors : 128
-------test 0--------
2 0
$
2
-------test 1--------
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
$
14
-------test 2--------
4 1
4 1 4 4
$
8
**/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |