#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 100000000000000000
typedef long long ll;
using namespace std;
struct point{
ll x1,y1,x2,y2;
};
point p[100001];
ll n,k;
ll solve(ll x,ll y,ll sz){
if(x==n+1 || y==n+1) return (ll)0;
ll black=0;
ll xx=((x+sz-1)/sz)*sz;
ll yy=((y+sz-1)/sz)*sz;
// cout << xx << ' ' << yy << '\n';
ll a=(n-xx)/sz;
ll b=(n-yy)/sz;
black+=(((a*b+1)/2)*sz*sz);
ll c=xx-x+1;
ll d=yy-y+1;
ll aa,bb;
if(a%2) bb=b/2;
else bb=(b+1)/2;
if(b%2) aa=a/2;
else aa=(a+1)/2;
black+=(bb*c*sz);
black+=(aa*d*sz);
if((xx/sz+yy/sz)%2==0) black+=(c*d);
return black;
}
int main(){
//ios_base::sync_with_stdio(NULL);
// cin.tie(NULL);
// cout.tie(NULL);
cin >> n >> k;
for(ll i=1;i<=k;i++){
cin >> p[i].x1 >> p[i].y1 >> p[i].x2 >> p[i].y2;
}
ll ans=INF;
// cout << solve(4,1,) << '\n';
for(ll i=1;i<n;i++){
if(n%i==0){
ll black=0,white=0;
for(ll j=1;j<=k;j++){
ll z=(solve(p[j].x1,p[j].y1,i)-solve(p[j].x1,p[j].y2+1,i)-solve(p[j].x2+1,p[j].y1,i)+solve(p[j].x2+1,p[j].y2+1,i));
black+=(z);
white+=((p[j].x2+1-p[j].x1)*(p[j].y2+1-p[j].y1)-z);
// if(i==2) cout << white << '\n';
}
// cout << black << ' ' << white << '\n';
if((n/i)%2){
ans=min(ans,((n*n+i*i)/2-black+white));
ans=min(ans,((n*n-i*i)/2-white+black));
}
else ans=min(ans,n*n/2-abs(black-white));
}
}
cout << ans;
}
# |
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 |
384 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
3820 KB |
Output is correct |
2 |
Correct |
23 ms |
1260 KB |
Output is correct |
3 |
Correct |
54 ms |
2540 KB |
Output is correct |
4 |
Correct |
53 ms |
2668 KB |
Output is correct |
5 |
Correct |
73 ms |
3308 KB |
Output is correct |
6 |
Correct |
46 ms |
2284 KB |
Output is correct |
7 |
Correct |
10 ms |
768 KB |
Output is correct |
8 |
Correct |
49 ms |
2268 KB |
Output is correct |
9 |
Correct |
118 ms |
5228 KB |
Output is correct |
10 |
Correct |
66 ms |
3068 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 |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
2 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 |
2 ms |
364 KB |
Output is correct |
14 |
Correct |
2 ms |
364 KB |
Output is correct |
15 |
Correct |
2 ms |
384 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 |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
2 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 |
2 ms |
364 KB |
Output is correct |
14 |
Correct |
2 ms |
364 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
35 ms |
1644 KB |
Output is correct |
17 |
Correct |
89 ms |
4332 KB |
Output is correct |
18 |
Correct |
126 ms |
5068 KB |
Output is correct |
19 |
Correct |
338 ms |
4716 KB |
Output is correct |
20 |
Correct |
371 ms |
5100 KB |
Output is correct |
21 |
Correct |
87 ms |
4204 KB |
Output is correct |
22 |
Correct |
2 ms |
384 KB |
Output is correct |
23 |
Correct |
72 ms |
2412 KB |
Output is correct |
24 |
Correct |
115 ms |
4588 KB |
Output is correct |
25 |
Correct |
15 ms |
748 KB |
Output is correct |
26 |
Correct |
72 ms |
3052 KB |
Output is correct |
27 |
Correct |
101 ms |
3564 KB |
Output is correct |
28 |
Correct |
127 ms |
4844 KB |
Output is correct |
29 |
Correct |
36 ms |
1900 KB |
Output is correct |
30 |
Correct |
4 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
3820 KB |
Output is correct |
2 |
Correct |
23 ms |
1260 KB |
Output is correct |
3 |
Correct |
54 ms |
2540 KB |
Output is correct |
4 |
Correct |
53 ms |
2668 KB |
Output is correct |
5 |
Correct |
73 ms |
3308 KB |
Output is correct |
6 |
Correct |
46 ms |
2284 KB |
Output is correct |
7 |
Correct |
10 ms |
768 KB |
Output is correct |
8 |
Correct |
49 ms |
2268 KB |
Output is correct |
9 |
Correct |
118 ms |
5228 KB |
Output is correct |
10 |
Correct |
66 ms |
3068 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 |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
2 ms |
364 KB |
Output is correct |
18 |
Correct |
2 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 |
2 ms |
364 KB |
Output is correct |
24 |
Correct |
2 ms |
364 KB |
Output is correct |
25 |
Correct |
2 ms |
384 KB |
Output is correct |
26 |
Correct |
35 ms |
1644 KB |
Output is correct |
27 |
Correct |
89 ms |
4332 KB |
Output is correct |
28 |
Correct |
126 ms |
5068 KB |
Output is correct |
29 |
Correct |
338 ms |
4716 KB |
Output is correct |
30 |
Correct |
371 ms |
5100 KB |
Output is correct |
31 |
Correct |
87 ms |
4204 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
72 ms |
2412 KB |
Output is correct |
34 |
Correct |
115 ms |
4588 KB |
Output is correct |
35 |
Correct |
15 ms |
748 KB |
Output is correct |
36 |
Correct |
72 ms |
3052 KB |
Output is correct |
37 |
Correct |
101 ms |
3564 KB |
Output is correct |
38 |
Correct |
127 ms |
4844 KB |
Output is correct |
39 |
Correct |
36 ms |
1900 KB |
Output is correct |
40 |
Correct |
4 ms |
492 KB |
Output is correct |
41 |
Correct |
318 ms |
4972 KB |
Output is correct |
42 |
Correct |
148 ms |
5484 KB |
Output is correct |
43 |
Correct |
203 ms |
4972 KB |
Output is correct |
44 |
Correct |
144 ms |
5356 KB |
Output is correct |
45 |
Correct |
130 ms |
5760 KB |
Output is correct |
46 |
Correct |
360 ms |
5484 KB |
Output is correct |
47 |
Correct |
117 ms |
5100 KB |
Output is correct |
48 |
Correct |
174 ms |
5100 KB |
Output is correct |
49 |
Correct |
134 ms |
4972 KB |
Output is correct |
50 |
Correct |
1400 ms |
5400 KB |
Output is correct |
51 |
Correct |
1472 ms |
5740 KB |
Output is correct |
52 |
Correct |
1386 ms |
5356 KB |
Output is correct |
53 |
Correct |
1473 ms |
5740 KB |
Output is correct |
54 |
Correct |
1360 ms |
5356 KB |
Output is correct |
55 |
Correct |
1536 ms |
5996 KB |
Output is correct |
56 |
Correct |
1333 ms |
5228 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 |
384 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 |
84 ms |
3820 KB |
Output is correct |
10 |
Correct |
23 ms |
1260 KB |
Output is correct |
11 |
Correct |
54 ms |
2540 KB |
Output is correct |
12 |
Correct |
53 ms |
2668 KB |
Output is correct |
13 |
Correct |
73 ms |
3308 KB |
Output is correct |
14 |
Correct |
46 ms |
2284 KB |
Output is correct |
15 |
Correct |
10 ms |
768 KB |
Output is correct |
16 |
Correct |
49 ms |
2268 KB |
Output is correct |
17 |
Correct |
118 ms |
5228 KB |
Output is correct |
18 |
Correct |
66 ms |
3068 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 |
2 ms |
384 KB |
Output is correct |
23 |
Correct |
2 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
2 ms |
364 KB |
Output is correct |
26 |
Correct |
2 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 |
2 ms |
364 KB |
Output is correct |
32 |
Correct |
2 ms |
364 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
35 ms |
1644 KB |
Output is correct |
35 |
Correct |
89 ms |
4332 KB |
Output is correct |
36 |
Correct |
126 ms |
5068 KB |
Output is correct |
37 |
Correct |
338 ms |
4716 KB |
Output is correct |
38 |
Correct |
371 ms |
5100 KB |
Output is correct |
39 |
Correct |
87 ms |
4204 KB |
Output is correct |
40 |
Correct |
2 ms |
384 KB |
Output is correct |
41 |
Correct |
72 ms |
2412 KB |
Output is correct |
42 |
Correct |
115 ms |
4588 KB |
Output is correct |
43 |
Correct |
15 ms |
748 KB |
Output is correct |
44 |
Correct |
72 ms |
3052 KB |
Output is correct |
45 |
Correct |
101 ms |
3564 KB |
Output is correct |
46 |
Correct |
127 ms |
4844 KB |
Output is correct |
47 |
Correct |
36 ms |
1900 KB |
Output is correct |
48 |
Correct |
4 ms |
492 KB |
Output is correct |
49 |
Correct |
318 ms |
4972 KB |
Output is correct |
50 |
Correct |
148 ms |
5484 KB |
Output is correct |
51 |
Correct |
203 ms |
4972 KB |
Output is correct |
52 |
Correct |
144 ms |
5356 KB |
Output is correct |
53 |
Correct |
130 ms |
5760 KB |
Output is correct |
54 |
Correct |
360 ms |
5484 KB |
Output is correct |
55 |
Correct |
117 ms |
5100 KB |
Output is correct |
56 |
Correct |
174 ms |
5100 KB |
Output is correct |
57 |
Correct |
134 ms |
4972 KB |
Output is correct |
58 |
Correct |
1400 ms |
5400 KB |
Output is correct |
59 |
Correct |
1472 ms |
5740 KB |
Output is correct |
60 |
Correct |
1386 ms |
5356 KB |
Output is correct |
61 |
Correct |
1473 ms |
5740 KB |
Output is correct |
62 |
Correct |
1360 ms |
5356 KB |
Output is correct |
63 |
Correct |
1536 ms |
5996 KB |
Output is correct |
64 |
Correct |
1333 ms |
5228 KB |
Output is correct |
65 |
Correct |
1 ms |
364 KB |
Output is correct |
66 |
Correct |
1 ms |
364 KB |
Output is correct |
67 |
Correct |
1444 ms |
5664 KB |
Output is correct |
68 |
Correct |
1440 ms |
5612 KB |
Output is correct |
69 |
Correct |
1260 ms |
4884 KB |
Output is correct |
70 |
Correct |
1352 ms |
5448 KB |
Output is correct |
71 |
Correct |
1359 ms |
5228 KB |
Output is correct |
72 |
Correct |
1316 ms |
5300 KB |
Output is correct |
73 |
Correct |
1306 ms |
5180 KB |
Output is correct |
74 |
Correct |
1421 ms |
5480 KB |
Output is correct |
75 |
Correct |
1339 ms |
5312 KB |
Output is correct |
76 |
Correct |
1434 ms |
5676 KB |
Output is correct |
77 |
Correct |
288 ms |
5928 KB |
Output is correct |
78 |
Correct |
139 ms |
5356 KB |
Output is correct |
79 |
Correct |
207 ms |
4972 KB |
Output is correct |
80 |
Correct |
219 ms |
5272 KB |
Output is correct |
81 |
Correct |
203 ms |
5016 KB |
Output is correct |
82 |
Correct |
188 ms |
5612 KB |
Output is correct |
83 |
Correct |
156 ms |
5220 KB |
Output is correct |
84 |
Correct |
895 ms |
5740 KB |
Output is correct |
85 |
Correct |
1521 ms |
5948 KB |
Output is correct |
86 |
Correct |
3 ms |
364 KB |
Output is correct |
87 |
Correct |
1 ms |
364 KB |
Output is correct |
88 |
Correct |
1536 ms |
5896 KB |
Output is correct |
89 |
Correct |
290 ms |
1388 KB |
Output is correct |
90 |
Correct |
1 ms |
364 KB |
Output is correct |