#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;
int n, k1;
pii p[N], q[N];
vector <ll> v;
ll ans = 1e18, a[N];
int main () {
// freopen ("input.txt", "r", stdin);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k1;
for (int i = 1; i < n; ++i) {
if (n % i == 0) {
v.pb (i);
}
}
ll k = 0;
for (int i = 1; i <= k1; ++i) {
cin >> p[i].ff >> p[i].ss >> q[i].ff >> q[i].ss;
k += (q[i].ff - p[i].ff + 1) * (q[i].ss - p[i].ss + 1);
}
// cout << "\n";
// for (int i = 1; i <= k1; ++i) {
// cout << p[i].ff << " " << p[i].ss << " " << q[i].ff << " " << q[i].ss << "\n";
// }
// cout << "\n\n\n";
for (ll bol : v) {
// 1-nji ak bolsa
for (int i = 1; i <= n; ++i) {
a[i] = ((i + bol - 1) / bol) % 2;
a[i] += a[i - 1];
}
// ilki 1-nji block gara renkde bolsa shol variant-da seretyas
ll jogap = 0, ak = 0;
ll opyshy_gara = (a[n] * a[n]) + (n - a[n]) * (n - a[n]);
for (int i = 1; i <= k1; ++i) {
ll val1 = (a[q[i].ss] - a[p[i].ss - 1]) * (a[q[i].ff] - a[p[i].ff - 1]);
ll val2 = (q[i].ss - p[i].ss + 1) - (a[q[i].ss] - a[p[i].ss - 1]);
ll val3 = (q[i].ff - p[i].ff + 1) - (a[q[i].ff] - a[p[i].ff - 1]);
val2 *= val3;
ll val4 = (q[i].ff - p[i].ff + 1) * (q[i].ss - p[i].ss + 1);
// if (p[i].ff == 3 and p[i].ff == 6) {
// cout << "men->" << val1 << " " << val2 << " " << val4 << "\n";
// return 0;
// }
ak += val4 - (val2 + val1);
}
jogap = (opyshy_gara - k) + (ak * 2LL);
// if (bol == 2) {
// cout << opyshy_gara << " " << ak << " " << k << "\n";
// dur1;
// }
// indi gara etyas
ak = 0;
opyshy_gara = (n * n) - opyshy_gara;
for (int i = 1; i <= k1; ++i) {
ll val1 = (a[q[i].ss] - a[p[i].ss - 1]) * (a[q[i].ff] - a[p[i].ff - 1]);
ll val2 = (q[i].ss - p[i].ss + 1) - (a[q[i].ss] - a[p[i].ss - 1]);
ll val3 = (q[i].ff - p[i].ff + 1) - (a[q[i].ff] - a[p[i].ff - 1]);
val2 *= val3;
ll val4 = (q[i].ff - p[i].ff + 1) * (q[i].ss - p[i].ss + 1);
ak += val2 + val1;
}
ll jogap1 = (opyshy_gara - k) + (ak * 2LL);
ans = min ({ans, jogap, jogap1});
}
cout << ans << "\n";
}
# | 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... |