#include <iostream>
#include <cassert>
#define int long long int
#define ericxiao ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int maxN = 1e5 + 326;
struct Rect{
int l, r, d, u, A;
Rect(){}
Rect(int l, int r, int d, int u): l(l), r(r), d(d), u(u){
A = (r - l + 1) * (u - d + 1);
}
} rects[maxN];
inline bool onDiag(int x, int y, int d){
return (((x % (2 * d)) < d) == ((y % (2 * d)) < d));
}
inline int id(int x, int y, int d){
return x / d * maxN + y / d;
}
inline int getArea(int a, int b){
if(a < 0 || b < 0) return 0;
return a * b;
}
inline int Area(int l, int r, int d, int u, int div){
int _l = (l + div - 1) / div * div, _r = r / div * div, _u = u / div * div, _d = (d + div - 1) / div * div, res = 0;
if((l / div == r / div) && (u / div == d / div)){
return (u - d + 1) * (r - l + 1) * onDiag(l, u, div);
}
if(l / div == r / div){
int k = 0;
k += (u - _u + 1) * onDiag(l, u, div);
k += (_d - d) * onDiag(l, d, div);
if(onDiag(l, _d, div) && ((_u - _d) / div) & 1) k += ((_u - _d) / div / 2 + 1) * d;
else k += ((_u - _d) / div / 2) * d;
return k * (r - l + 1);
}
if(u / div == d / div){
int k = 0;
k += (_l - l) * onDiag(l, u, div);
k += (r - _r + 1) * onDiag(r, u, div);
if(onDiag(_l, u, div) && ((_r - _l) / div) & 1) k += ((_r - _l) / div / 2 + 1) * d;
else k += ((_r - _l) / div / 2) * d;
return k * (u - d + 1);
}
assert(false);
res = (_r - _l) * (_u - _d);
if(onDiag(_l, _u, div)) res = (res + 1) / 2;
else res = res / 2;
if(onDiag(l, u, div)){
res += getArea((_l - l), (u - _u));
res += getArea((u - _u), (_r - _l) / div / 2 * div);
} else {
res += getArea((u - _u), ((_r - _l) / div + 1) / 2 * div);
}
if(onDiag(r, u, div)){
res += getArea((r - _r), (u - _u));
res += getArea((r - _r), (_u - _d) / div / 2 * div);
} else {
res += (r - _r) * ((_u - _d) / div + 1) / 2 * div;
}
if(onDiag(r, d, div)){
res += getArea((r - _r), (_d - d));
res += getArea((_d - d), (_r - _l) / div / 2 * div);
} else {
res += getArea((_d - d), ((_r - _l) / div + 1) / 2 * div);
}
if(onDiag(l, d, div)){
res += getArea((_l - l), (_d - d));
res += getArea((_l - l), (_u - _d) / div / 2 * div);
} else {
res += getArea((_l - l), ((_u - _d) / div + 1) / 2 * div);
}
return res;
}
int N, K;
inline int check(int d){
//top left is black
//cout << "d = " << d << endl;
int _ans = maxN * maxN, tmp = ((N / d) * (N / d) + 1) / 2 * (d * d), tmp2 = ((N / d) * (N / d)) / 2 * (d * d);
//cout << "1tmp = " << tmp << endl;
for(int i = 0; i < K; i++){
int A = Area(rects[i].l, rects[i].r, rects[i].d, rects[i].u, d), B = rects[i].A - A;
tmp += B - A;
tmp2 += A - B;
}
return min(tmp, tmp2);
//top right is black
}
signed main(){
ericxiao;
cin >> N >> K;
int l, r, d, u;
for(int i = 0; i < K; i++){
cin >> l >> d >> r >> u;
l--; d--; r--; u--;
rects[i] = Rect(l, r, d, u);
//cout << "rects[i] a = " << rects[i].A << endl;
}
int ans = maxN * maxN;
for(int div = 1; div * div <= N; div++){
if(!(N % div)){
ans = min(ans, check(div));
if(div != 1) ans = min(ans, check(N / div));
}
}
cout << ans << endl;
}
/*
*
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
*/
Compilation message
chessboard.cpp: In function 'long long int check(long long int)':
chessboard.cpp:88:6: warning: unused variable '_ans' [-Wunused-variable]
88 | int _ans = maxN * maxN, tmp = ((N / d) * (N / d) + 1) / 2 * (d * d), tmp2 = ((N / d) * (N / d)) / 2 * (d * d);
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
2796 KB |
Output is correct |
2 |
Correct |
7 ms |
1004 KB |
Output is correct |
3 |
Correct |
17 ms |
1900 KB |
Output is correct |
4 |
Correct |
18 ms |
2156 KB |
Output is correct |
5 |
Correct |
26 ms |
2540 KB |
Output is correct |
6 |
Correct |
15 ms |
1644 KB |
Output is correct |
7 |
Correct |
4 ms |
620 KB |
Output is correct |
8 |
Correct |
15 ms |
1644 KB |
Output is correct |
9 |
Correct |
42 ms |
3820 KB |
Output is correct |
10 |
Correct |
21 ms |
2284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
12 ms |
1388 KB |
Output is correct |
17 |
Correct |
30 ms |
3740 KB |
Output is correct |
18 |
Correct |
42 ms |
4204 KB |
Output is correct |
19 |
Correct |
114 ms |
3820 KB |
Output is correct |
20 |
Correct |
124 ms |
4204 KB |
Output is correct |
21 |
Correct |
29 ms |
3564 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
25 ms |
2028 KB |
Output is correct |
24 |
Correct |
40 ms |
3820 KB |
Output is correct |
25 |
Correct |
5 ms |
620 KB |
Output is correct |
26 |
Correct |
24 ms |
2540 KB |
Output is correct |
27 |
Correct |
35 ms |
3052 KB |
Output is correct |
28 |
Correct |
44 ms |
4204 KB |
Output is correct |
29 |
Correct |
16 ms |
1644 KB |
Output is correct |
30 |
Correct |
2 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
2796 KB |
Output is correct |
2 |
Correct |
7 ms |
1004 KB |
Output is correct |
3 |
Correct |
17 ms |
1900 KB |
Output is correct |
4 |
Correct |
18 ms |
2156 KB |
Output is correct |
5 |
Correct |
26 ms |
2540 KB |
Output is correct |
6 |
Correct |
15 ms |
1644 KB |
Output is correct |
7 |
Correct |
4 ms |
620 KB |
Output is correct |
8 |
Correct |
15 ms |
1644 KB |
Output is correct |
9 |
Correct |
42 ms |
3820 KB |
Output is correct |
10 |
Correct |
21 ms |
2284 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
12 ms |
1388 KB |
Output is correct |
27 |
Correct |
30 ms |
3740 KB |
Output is correct |
28 |
Correct |
42 ms |
4204 KB |
Output is correct |
29 |
Correct |
114 ms |
3820 KB |
Output is correct |
30 |
Correct |
124 ms |
4204 KB |
Output is correct |
31 |
Correct |
29 ms |
3564 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
25 ms |
2028 KB |
Output is correct |
34 |
Correct |
40 ms |
3820 KB |
Output is correct |
35 |
Correct |
5 ms |
620 KB |
Output is correct |
36 |
Correct |
24 ms |
2540 KB |
Output is correct |
37 |
Correct |
35 ms |
3052 KB |
Output is correct |
38 |
Correct |
44 ms |
4204 KB |
Output is correct |
39 |
Correct |
16 ms |
1644 KB |
Output is correct |
40 |
Correct |
2 ms |
492 KB |
Output is correct |
41 |
Correct |
106 ms |
3564 KB |
Output is correct |
42 |
Correct |
49 ms |
3948 KB |
Output is correct |
43 |
Correct |
71 ms |
3564 KB |
Output is correct |
44 |
Correct |
45 ms |
3948 KB |
Output is correct |
45 |
Correct |
41 ms |
4204 KB |
Output is correct |
46 |
Correct |
129 ms |
3948 KB |
Output is correct |
47 |
Correct |
37 ms |
3692 KB |
Output is correct |
48 |
Correct |
57 ms |
3692 KB |
Output is correct |
49 |
Correct |
42 ms |
3564 KB |
Output is correct |
50 |
Correct |
478 ms |
3948 KB |
Output is correct |
51 |
Correct |
525 ms |
4180 KB |
Output is correct |
52 |
Correct |
479 ms |
3920 KB |
Output is correct |
53 |
Correct |
510 ms |
4076 KB |
Output is correct |
54 |
Correct |
471 ms |
3948 KB |
Output is correct |
55 |
Correct |
526 ms |
4300 KB |
Output is correct |
56 |
Correct |
456 ms |
3768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
9 |
Correct |
27 ms |
2796 KB |
Output is correct |
10 |
Correct |
7 ms |
1004 KB |
Output is correct |
11 |
Correct |
17 ms |
1900 KB |
Output is correct |
12 |
Correct |
18 ms |
2156 KB |
Output is correct |
13 |
Correct |
26 ms |
2540 KB |
Output is correct |
14 |
Correct |
15 ms |
1644 KB |
Output is correct |
15 |
Correct |
4 ms |
620 KB |
Output is correct |
16 |
Correct |
15 ms |
1644 KB |
Output is correct |
17 |
Correct |
42 ms |
3820 KB |
Output is correct |
18 |
Correct |
21 ms |
2284 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
12 ms |
1388 KB |
Output is correct |
35 |
Correct |
30 ms |
3740 KB |
Output is correct |
36 |
Correct |
42 ms |
4204 KB |
Output is correct |
37 |
Correct |
114 ms |
3820 KB |
Output is correct |
38 |
Correct |
124 ms |
4204 KB |
Output is correct |
39 |
Correct |
29 ms |
3564 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
41 |
Correct |
25 ms |
2028 KB |
Output is correct |
42 |
Correct |
40 ms |
3820 KB |
Output is correct |
43 |
Correct |
5 ms |
620 KB |
Output is correct |
44 |
Correct |
24 ms |
2540 KB |
Output is correct |
45 |
Correct |
35 ms |
3052 KB |
Output is correct |
46 |
Correct |
44 ms |
4204 KB |
Output is correct |
47 |
Correct |
16 ms |
1644 KB |
Output is correct |
48 |
Correct |
2 ms |
492 KB |
Output is correct |
49 |
Correct |
106 ms |
3564 KB |
Output is correct |
50 |
Correct |
49 ms |
3948 KB |
Output is correct |
51 |
Correct |
71 ms |
3564 KB |
Output is correct |
52 |
Correct |
45 ms |
3948 KB |
Output is correct |
53 |
Correct |
41 ms |
4204 KB |
Output is correct |
54 |
Correct |
129 ms |
3948 KB |
Output is correct |
55 |
Correct |
37 ms |
3692 KB |
Output is correct |
56 |
Correct |
57 ms |
3692 KB |
Output is correct |
57 |
Correct |
42 ms |
3564 KB |
Output is correct |
58 |
Correct |
478 ms |
3948 KB |
Output is correct |
59 |
Correct |
525 ms |
4180 KB |
Output is correct |
60 |
Correct |
479 ms |
3920 KB |
Output is correct |
61 |
Correct |
510 ms |
4076 KB |
Output is correct |
62 |
Correct |
471 ms |
3948 KB |
Output is correct |
63 |
Correct |
526 ms |
4300 KB |
Output is correct |
64 |
Correct |
456 ms |
3768 KB |
Output is correct |
65 |
Correct |
1 ms |
364 KB |
Output is correct |
66 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
67 |
Halted |
0 ms |
0 KB |
- |