#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point {
ll x, y;
};
// returns number of black ceils on chess board a x b, f - color of first ceil (0 - white, 1 - black)
ll black_nums(ll a, ll b, bool f) {
if(a < 0 || b < 0) return 0;
if(f) return ((a + 1) >> 1) * ((b + 1) >> 1) + (a >> 1) * (b >> 1);
return (a >> 1) * ((b + 1) >> 1) + ((a + 1) >> 1) * (b >> 1);
}
ll func(point p1, point p2, ll d, bool cl) {
ll cp1y = p1.y / d, cp1x = p1.x / d, cp2x = p2.x / d, cp2y = p2.y / d;
ll x1 = p1.x, x2 = p2.x, y1 = p1.y, y2 = p2.y;
ll dx1 = ((d - p1.x % d) % d);
ll dy1 = ((d - p1.y % d) % d);
ll dx2 = ((p2.x + 1) % d);
ll dy2 = ((p2.y + 1) % d);
if((dx1 || dx2) && cp1x == cp2x) dx1 = p2.x - p1.x + 1, dx2 = 0;
x1 += dx1; x2 -= dx2;
if((dx1 || dx2) && cp1y == cp2y) dy1 = p2.y - p1.y + 1, dy2 = 0;
y1 += dy1; y2 -= dy2;
ll cx1 = x1 / d, cy1 = y1 / d;
ll cnt = 0;
cnt += black_nums((x2 - x1 + 1) / d, (y2 - y1 + 1) / d, (cl ^ ((cx1 + cy1) & 1))) * d * d;
cnt += black_nums((x2 - x1 + 1) / d, 1, (cl ^ ((cx1 + cp1y) & 1))) * dy1 * d;
cnt += black_nums((x2 - x1 + 1) / d, 1, (cl ^ ((cx1 + cp2y) & 1))) * dy2 * d;
cnt += black_nums(1, (y2 - y1 + 1) / d, (cl ^ ((cp1x + cy1) & 1))) * dx1 * d;
cnt += black_nums(1, (y2 - y1 + 1) / d, (cl ^ ((cp2x + cy1) & 1))) * dx2 * d;
cnt += (cl ^ ((cp1x + cp1y) & 1)) * dx1 * dy1;
if(p2.x > p1.x) cnt += (cl ^ ((cp2x + cp1y) & 1)) * dx2 * dy1;
if(p2.y > p1.y) cnt += (cl ^ ((cp1x + cp2y) & 1)) * dx1 * dy2;
if(p2.x > p1.x && p2.y > p1.y) cnt += (cl ^ ((cp2x + cp2y) & 1)) * dx2 * dy2;
return cnt;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll n, k;
cin >> n >> k;
point v1[k], v2[k];
for(int i = 0; i < k; i++) {
point p1, p2;
cin >> p1.x >> p1.y;
p1.x--; p1.y--;
cin >> p2.x >> p2.y;
p2.x--; p2.y--;
v1[i] = p1; v2[i] = p2;
}
ll ans = n * n;
for(ll D = 1; D <= n; D++) {
if(n % D) continue;
ll d = D;
ll val1 = 0, val2 = 0;
val1 = black_nums(n / d, n / d, 1) * d * d;
val2 = black_nums(n / d, n / d, 0) * d * d;
for(int i = 0; i < k; i++) {
val1 += (v2[i].x - v1[i].x + 1) * (v2[i].y - v1[i].y + 1) - 2 * func(v1[i], v2[i], d, 1);
val2 += (v2[i].x - v1[i].x + 1) * (v2[i].y - v1[i].y + 1) - 2 * func(v1[i], v2[i], d, 0);
}
ans = min(ans, val1);
ans = min(ans, val2);
if(D == 1) continue;
d = n / D;
val1 = black_nums(n / d, n / d, 1) * d * d;
val2 = black_nums(n / d, n / d, 0) * d * d;
for(int i = 0; i < k; i++) {
val1 += (v2[i].x - v1[i].x + 1) * (v2[i].y - v1[i].y + 1) - 2 * func(v1[i], v2[i], d, 1);
val2 += (v2[i].x - v1[i].x + 1) * (v2[i].y - v1[i].y + 1) - 2 * func(v1[i], v2[i], d, 0);
}
ans = min(ans, val1);
ans = min(ans, val2);
}
cout << ans;
}
| # |
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 |
47 ms |
2260 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 |
47 ms |
2260 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 |
- |
