#include <bits/stdc++.h>
//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define int long long
using namespace std;
//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 1e6 + 100;
const int M = 21890;
const ll mod = 1e9 + 7;
const ll MOD = 998244353;
const int P = 1336;
const ld eps = 0.000000001;
const int inf = 1e9 + 7;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
int l1[N], r1[N], l2[N], r2[N];
int m;
pair <int, pair <int, int> > get(int r, int x, int y, int fl)
{
int x1 = x / r;
if (x % r) x1++;
int y1 = y / r;
if (y % r) y1++;
int f = y1 % 2;
if (x1 % 2 == 0)
{
f = !f;
}
int kx = x / r;
if (x % r) kx++;
int nx = kx * r - x + 1;
int ky = y / r;
if (y % r) ky++;
int ny = ky * r - y + 1;
if (fl) return {!f, {nx, ny}};
}
int solve(int r, int x1, int y1, int x2, int y2, bool fl)
{
if (x1 > x2 || y1 > y2) return 0;
int vs = 0;
int bx1 = x1 / r, bx2 = x2 / r;
if (x1 % r < 2) bx1++;
else bx1 += 2;
int by1 = y1 / r, by2 = y2 / r;
if (y1 % r < 2) by1++;
else by1 += 2;
if (r == 1)
{
bx1 = x1; by1 = y1; bx2 = x2; by2 = y2;
}
// cout << "! " << bx1 << " " << bx2 << " " << by1 << " " << by2 << endl;
if (bx1 > bx2 || by1 > by2)
{
if (bx1 > bx2 && by1 > by2)
{
int vs = 0;
pair < int, pair < int, int > > p = get(r, x1, y1, fl);
// cout << p.F << " " << p.S.F << " " << p.S.S << endl;
p.S.F = min(p.S.F, x2 - x1 + 1);
p.S.S = min(p.S.S, y2 - y1 + 1);
if (p.F != fl) vs += p.S.F * p.S.S;
pair < int, pair < int, int > > p1 = get(r, x1, y1 + p.S.S + 1, fl);
p1.S.F = min(p1.S.F, max(0ll, x2 - x1 + 1));
p1.S.S = min(p1.S.S, max(0ll, y2 - (y1 + p.S.S) + 1));
// cout << p1.F << " " << p1.S.F << " " << p1.S.S << endl;
if (p1.F != fl) vs += p1.S.F * p1.S.S;
p1 = get(r, x1 + p.S.F + 1, y1, fl);
p1.S.F = min(p1.S.F, max(0ll, x2 - (x1 + p.S.F) + 1));
p1.S.S = min(p1.S.S, max(0ll, y2 - y1 + 1));
// cout << p1.F << " " << p1.S.F << " " << p1.S.S << endl;
if (p1.F != fl) vs += p1.S.F * p1.S.S;
p1 = get(r, x1 + p.S.F + 1, y1 + p.S.S + 1, fl);
p1.S.F = min(p1.S.F, max(0ll, x2 - (x1 + p.S.F) + 1));
p1.S.S = min(p1.S.S, max(0ll, y2 - (y1 + p.S.S) + 1));
// cout << p1.F << " " << p1.S.F << " " << p1.S.S << endl;
if (p1.F != fl) vs += p1.S.F * p1.S.S;
return vs;
}
if (bx1 > bx2)
{
int sty = (by1 - 1) * r + 1;
// cout << sty << endl;
pair < int, pair < int, int > > p = get(r, x1, sty, fl);
int vs = 0, ch = 0;
p.S.F = min(p.S.F, x2 - x1 + 1);
p.S.S = min(p.S.S, y2 - y1 + 1);
vs = p.S.F * p.S.S;
ch = (x2 - x1 + 1) * r - p.S.F * p.S.S;
int k = (by2 - by1 + 1 + 1) / 2;
int S1 = vs * k + ch * (by2 - by1 + 1 - k);
int S2 = ch * k + vs * (by2 - by1 + 1 - k);
// cout << S1 << " " << S2 << endl;
int add = solve(r, x1, y1, x2, sty - 1, fl);
int ey = by2 * r;
add += solve(r, x1, ey + 1, x2, y2, fl);
if (p.F == fl) return S2 + add;
else return S1 + add;
}
if (by1 > by2)
{
int stx = (bx1 - 1) * r + 1;
cout << stx << endl;
pair < int, pair < int, int > > p = get(r, stx, y1, fl);
int vs = 0, ch = 0;
p.S.F = min(p.S.F, x2 - x1 + 1);
p.S.S = min(p.S.S, y2 - y1 + 1);
vs = p.S.F * p.S.S;
ch = (y2 - y1 + 1) * r - p.S.F * p.S.S;
int k = (bx2 - bx1 + 1 + 1) / 2;
int S1 = vs * k + ch * (bx2 - bx1 + 1 - k);
int S2 = ch * k + vs * (bx2 - bx1 + 1 - k);
// cout << S1 << " " << S2 << endl;
int add = solve(r, x1, y1, stx - 1, y2, fl);
int ex = bx2 * r;
add += solve(r, ex + 1,y1, x2, y2, fl);
if (p.F == fl) return S2 + add;
else return S1 + add;
}
return 0;
}
int x = (bx2 - bx1 + 1 + 1) / 2;
int y = (by2 - by1 + 1 + 1) / 2;
int addx = bx2 - bx1 + 1 - x;
int addy = by2 - by1 + 1 - y;
int s = x * y + addx * addy;
// cout << "! " << s << endl;
bool f = 0;
if (fl == 0)
{
if (bx1 % 2)
{
if (by1 % 2 == 0) f = 1;
}
else if (by1 % 2) f = 1;
}
else
{
if (bx1 % 2)
{
if (by1 % 2) f = 1;
}
else if (by1 % 2 == 0) f = 1;
}
if (f == 0) vs += s * r * r;
else vs += ((bx2 - bx1 + 1) * (by2 - by1 + 1) * r * r - s * r * r);
int stx = (bx1 - 1) * r + 1;
int ex = bx2 * r;
int sty = (by1 - 1) * r + 1;
int ey = by2 * r;
int add = solve(r, x1, y1, stx - 1, y2, fl) +
solve(r, ex + 1, y1, x2, y2, fl) +
solve(r, stx, y1, ex, sty - 1, fl) +
solve(r, stx, ey + 1, ex, y2, fl);
// if (vs != 0) cout << f << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
return vs + add;
}
int get_ans(int d, int n)
{
int S = n * n;
n /= d;
int kol = (n + 1) / 2;
kol *= kol;
int c = n / 2;
c *= c;
int w = kol * d * d + c * d * d;
int s1 = 0, s2 = 0;
int sum1 = 0, sum2 = 0;
for(int i = 0; i < m; i++)
{
int v1 = solve(d, l1[i], r1[i], l2[i], r2[i], 1), v2 = solve(d, l1[i], r1[i], l2[i], r2[i], 0);
sum1 += (l2[i] - l1[i] + 1) * (r2[i] - r1[i] + 1) - v1;
sum2 += (l2[i] - l1[i] + 1) * (r2[i] - r1[i] + 1) - v2;
s1 += v1;
s2 += v2;
}
// cout << d << " " << s1 << " " << s2 << endl;
s1 += w - sum1;
s2 += (S - w) - sum2;
// cerr << S - w << " " << sum1 << " " << d << " " << s1 << " " << s2 << endl;
int ch = min(s1, s2);
return ch;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(time(0));
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int n;
cin >> n >> m;
for(int i = 0; i < m; i++)
{
cin >> l1[i] >> r1[i] >> l2[i] >> r2[i];
// cout << solve(1, l1[i], r1[i], l2[i], r2[i], 1) << endl;
}
int d = 1;
int ans = inf;
while (d * d <= n)
{
if (n % d == 0)
{
ans = min(ans, get_ans(d, n));
if (d != 1) ans = min(ans, get_ans(n / d, n));
}
d++;
}
cout << ans;
}
Compilation message
chessboard.cpp: In function 'std::pair<long long int, std::pair<long long int, long long int> > get(long long int, long long int, long long int, long long int)':
chessboard.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 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 |
252 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
348 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
2296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
2296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 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 |
252 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
348 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Incorrect |
35 ms |
2296 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
