#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
inline void solve() {
int n, m;
cin >> n >> m;
ve<pair<pii,pii>> a(m);
for (auto &[a1, a2] : a) {
auto &[x1, y1] = a1;
auto &[x2, y2] = a2;
cin >> x1 >> y1 >> x2 >> y2;
--x1, --y1, --x2, --y2;
}
auto even = [](ll l, ll r) { if (l > r) {return 0ll;} return r / 2 - (l + 1) / 2 + 1; };
auto odd = [&even](ll l, ll r) { if (l > r) {return 0ll;} return r - l + 1 - even(l, r); };
auto run = [&](int d) {
ll ans1 = 0, ans2 = 0;
for (auto &[a1, a2] : a) {
auto &[x1, y1] = a1;
auto &[x2, y2] = a2;
ll evx, odx, evy, ody;
{
ll mn = x1 / d, mx = x2 / d;
if (mn == mx) {
if (mn & 1) evx = 0, odx = x2 - x1 + 1;
else odx = 0, evx = x2 - x1 + 1;
}
else {
evx = odx = 0;
evx += d * even(mn + 1, mx - 1);
odx += d * odd(mn + 1, mx - 1);
if (mn & 1) odx += (mn + 1) * d - x1;
if (mx & 1) odx += x2 - mx * d + 1;
if (mn & 1 ^ 1) evx += (mn + 1) * d - x1;
if (mx & 1 ^ 1) evx += x2 - mx * d + 1;
}
}
{
ll mn = y1 / d, mx = y2 / d;
if (mn == mx) {
if (mn & 1) evy = 0, ody = y2 - y1 + 1;
else ody = 0, evy = y2 - y1 + 1;
}
else {
evy = ody = 0;
evy += d * even(mn + 1, mx - 1);
ody += d * odd(mn + 1, mx - 1);
if (mn & 1) ody += (mn + 1) * d - y1;
if (mx & 1) ody += y2 - mx * d + 1;
if (mn & 1 ^ 1) evy += (mn + 1) * d - y1;
if (mx & 1 ^ 1) evy += y2 - mx * d + 1;
}
}
// corner is white
ans1 += evx * evy + odx * ody;
ans1 -= (evx * ody + evy * odx);
// corner is black
ans2 += evx * ody + evy * odx;
ans2 -= (evx * evy + odx * ody);
}
ll e = even(1, n / d), o = odd(1, n / d);
ans1 += d * d * e * o;
ans2 += d * d * (e * e + o * o);
return min(ans1, ans2);
};
ll res = inf;
for (int d = 1; d * d <= n; ++d) {
if (n % d) continue;
chmin(res, run(d));
if (d * d != n && d > 1) chmin(res, run(n / d));
}
cout << res * 2ll;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
Compilation message
chessboard.cpp: In lambda function:
chessboard.cpp:59:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
59 | if (mn & 1 ^ 1) evx += (mn + 1) * d - x1;
| ~~~^~~
chessboard.cpp:60:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
60 | if (mx & 1 ^ 1) evx += x2 - mx * d + 1;
| ~~~^~~
chessboard.cpp:77:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
77 | if (mn & 1 ^ 1) evy += (mn + 1) * d - y1;
| ~~~^~~
chessboard.cpp:78:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
78 | if (mx & 1 ^ 1) evy += y2 - mx * d + 1;
| ~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
216 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
324 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
216 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
324 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
21 ms |
2764 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
