#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
#define int long long
using namespace std;
const int N = (1e5 + 12);
const int mod = (1e9 + 7);
const int INF = (0x3f3f3f3f);
int ans = 1e18;
int n, k, x[2][N], y[2][N];
int get(int x1, int y1, int x2, int y2, int div,int f){
int blx = (x1 + div - 1ll) / div, blx2 = (x2 + div - 1ll) / div;
int bly = (y1 + div - 1ll) / div, bly2 = (y2 + div - 1ll) / div;
int res = 0ll, odd, even;
cout << blx << " " << bly << " " << blx2 << " " << bly2 << endl;
if(blx == blx2){
int val = x2 - x1 + 1ll;
if(bly != bly2){
int end = bly * div;
val = val * (end - y1 + 1ll);
bly++;
if(bly2 > bly){
int dif = bly2 - bly;
val += dif / 2ll * ((x2 - x1 + 1ll) * div);
}
int start = (bly2 - 1ll) * div + 1ll;
int len = y2 - start + 1ll;
if((bly2 + blx) % 2ll == f){
val += len * (x2 - x1 + 1ll);
}
int p = (x2 - x1 + 1ll) * (y2 - y1 + 1ll);
p = p - val;
if(((bly - 1ll) + blx) % 2ll == f){
res += val;
}
else{
res += p;
}
}
else{
int p = (x2 - x1 + 1ll) * (y2 - y1 + 1ll);
if((bly + blx) % 2ll == f){
res += p;
}
}
}
else{
int end = blx * div;
int odd = end - x1 + 1ll;
blx++;
if(blx2 > blx){
int dif = blx2 - blx + 1ll;
odd += dif / 2ll * div;
}
int op = (x2 - x1 + 1);
op -= odd;
if(bly != bly2){
end = bly * div;
int val = end - y1 + 1ll;
val = val * odd;
bly++;
if(bly2 > bly){
int dif = bly2 - bly;
val += dif / 2ll * odd * div;
val += (dif - dif / 2ll) * op * div;
}
int start = (bly2 - 1) * div + 1;
int len = y2 - start + 1;
if((bly2 + blx - 1) % 2ll == f){
val += len * odd;
}
else{
val += len * op;
}
int p = (x2 - x1 + 1ll) * (y2 - y1 + 1ll);
p = p - val;
if((bly + blx) % 2ll == f){
res += val;
}
else{
res += p;
}
}
else{
if(((blx - 1ll) + bly) % 2ll == f){
res += odd;
}
else{
res += op;
}
}
}
return res;
}
void calc(int div){
int bl = n / div, cnt = 0ll, x1, y1, cnt1 = 0ll, x2, y2;
if(bl & 1ll){
cnt += div * div * ((bl + 1ll) / 2ll) * ((bl + 1ll) / 2ll);
cnt += div * div * (bl / 2ll) * (bl / 2);
cnt1 = n * n - cnt;
for(int i = 1;i <= k; i++){
x1 = x[0ll][i];
y1 = y[0ll][i];
x2 = x[1ll][i];
y2 = y[1ll][i];
cnt -= get(x1, y1, x2, y2, div, 0ll);
cnt += get(x1, y1, x2, y2, div, 1ll);
cnt1 += get(x1, y1, x2, y2, div, 0ll);
cnt1 -= get(x1, y1, x2, y2, div, 1ll);
}
ans = min(ans, cnt);
ans = min(ans, cnt1);
}
else{
cnt += div * div * (bl / 2ll) * bl;
cnt1 = n * n - cnt;
for(int i = 1ll;i <= k; i++){
x1 = x[0ll][i];
y1 = y[0ll][i];
x2 = x[1ll][i];
y2 = y[1ll][i];
cnt -= get(x1, y1, x2, y2, div, 0ll);
cnt += get(x1, y1, x2, y2, div, 1ll);
cnt1 += get(x1, y1, x2, y2, div, 0ll);
cnt1 -= get(x1, y1, x2, y2, div, 1ll);
}
ans = min(ans, cnt);
ans = min(ans, cnt1);
}
}
main()
{
cin >> n >> k;
for(int i = 1ll;i <= k; i++){
scanf("%lld%lld%lld%lld", &y[0ll][i], &x[0ll][i], &y[1ll][i], &x[1ll][i]);
}
//x1 = x[0ll][1];
//y1 = y[0ll][1];
//x2 = x[1ll][1];
//y2 = y[1ll][1];
//cout << get(x1, y1, x2, y2, 3ll, 0ll);
if(n % 2ll == 1ll){
int x1, y1, x2, y2;
int cnt = n * n / 2ll + 1ll, cnt1 = n * n / 2ll;
for(int i = 1;i <= k; i++){
x1 = x[0ll][i];
y1 = y[0ll][i];
x2 = x[1ll][i];
y2 = y[1ll][i];
cnt -= get(x1, y1, x2, y2, 1ll, 0ll);
cnt += get(x1, y1, x2, y2, 1ll, 1ll);
cnt1 += get(x1, y1, x2, y2, 1ll, 0ll);
cnt1 -= get(x1, y1, x2, y2, 1ll, 1ll);
}
ans = min(ans, cnt);
ans = min(ans, cnt1);
}
else{
int x1, y1,x2, y2;
int cnt = n * n / 2ll, cnt1 = n * n / 2ll;
for(int i = 1;i <= k; i++){
x1 = x[0ll][i];
y1 = y[0ll][i];
x2 = x[1ll][i];
y2 = y[1ll][i];
cnt -= get(x1, y1, x2, y2, 1ll, 0ll);
cnt += get(x1, y1, x2, y2, 1ll, 1ll);
cnt1 += get(x1, y1, x2, y2, 1ll, 0ll);
cnt1 -= get(x1, y1, x2, y2, 1ll, 1ll);
}
ans = min(ans, cnt);
ans = min(ans, cnt1);
}
for(int i = 2ll;i * i <= n; i++){
if(n % i == 0ll){
calc(i);
calc(n / i);
}
}
cout << ans;
}
/*
6 5
3 3 4 4
1 2 1 2
5 5 5 5
2 1 2 1
3 6 3 6
4 1
4 1 4 4
*/
Compilation message
chessboard.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int, long long int)':
chessboard.cpp:22:17: warning: unused variable 'odd' [-Wunused-variable]
int res = 0ll, odd, even;
^~~
chessboard.cpp:22:22: warning: unused variable 'even' [-Wunused-variable]
int res = 0ll, odd, even;
^~~~
chessboard.cpp: At global scope:
chessboard.cpp:141:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
chessboard.cpp: In function 'int main()':
chessboard.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld", &y[0ll][i], &x[0ll][i], &y[1ll][i], &x[1ll][i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
800 ms |
8440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
800 ms |
8440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Incorrect |
800 ms |
8440 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
