#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
const ll INF = 2e18;
const ll MOD = 1e9+7;
vector<pair<pair<ll, ll>, pair<ll, ll>>> a;
ll f(ll i, ll j, ll k){
ll ii = i-i%k, ij=j-j%k; ll iblock = ii/k, jblock = ij/k;
ll cnt = iblock/2*ij*k + iblock%2*k*k*(jblock/2+jblock%2)+((i-ii)*(jblock/2+(iblock%2==0 and jblock%2))+(j-ij)*(iblock/2+(jblock%2==0 and iblock%2)))*k+(1-((i/k+(i%k?1:0))+(j/k+(j%k?1:0)))%2)*(i-ii)*(j-ij);
return cnt;
}
ll calc(ll k, ll n){
ll res = f(n, n, k);
// cout << n << "-" << k << " " << res << ln;
ll bwc=0;
for (auto &ch:a){
ll contr = 2*(f(ch.ss.ff, ch.ss.ss, k)-f(ch.ff.ff-1, ch.ss.ss, k)-f(ch.ss.ff, ch.ff.ss-1, k)+f(ch.ff.ff-1, ch.ff.ss-1, k))-(ch.ss.ss-ch.ff.ss+1)*(ch.ss.ff-ch.ff.ff+1);
bwc += contr;
}
return min(res-bwc, n*n-res+bwc);
}
void solve(){
ll n, m; cin >> n >> m;
a.resize(m);
for (ll i=0; i<m; i++){
cin >> a[i].ff.ff >> a[i].ff.ss >> a[i].ss.ff >> a[i].ss.ss;
}
ll res=INF;
for (ll i=1; i*i<=n; i++){
if (n%i==0){
res=min(res, calc(i, n));
if (n/i!=n) res=min(res, calc(n/i, n));
}
}
cout << res << ln;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto start = chrono::high_resolution_clock::now();
ll t=1;
// cin >> t;
while (t--) solve();
#ifdef LOCAL
auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
#endif
}
# | 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... |