#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 gx = x / r + 1, gy = y / r + 1;
bool f;
if (fl == 0)
{
if (gx % 2)
{
if (gy % 2) f = 0;
else f = 1;
}
else if (gy % 2) f = 1;
else f = 0;
}
else
{
if (gx % 2)
{
if (gy % 2) f = 1;
else f = 0;
}
else if (gy % 2) f = 0;
else f = 1;
}
int bx = gx * r - gx + 1;
int by = gy * r - gy + 1;
return {f, {bx, by}};
}
int solve(int r, int x1, int y1, int x2, int y2, int fl)
{
int gx1 = x1 / r + 1, gx2 = x2 / r;
if (gx1 % r != 1) gx1++;
int gy1 = y1 / r + 1, gy2 = y2 / r;
if (gy1 % r != 1) gy1++;
if (r == 1)
{
gx1 = x1; gx2 = x2; gy1 = y1; gy2 = y2;
}
if (gx1 > gx2 || gy1 > gy2)
{
return 0;
}
int stx = gx1 * r - r + 1;
int ex = gx2 * r;
int sty = gy1 * r - r + 1;
int ey = gy2 * r;
int kolx = (gx2 - gx1 + 1 + 1) / 2;
int koly = (gy2 - gy1 + 1 + 1) / 2;
int S = kolx * koly * r * r;
kolx = (gx2 - gx1 + 1) / 2;
koly = (gy2 - gy1 + 1) / 2;
S += kolx * koly * r * r;
pair < int, pair <int, int> > p = get(r, stx, sty, fl);
// cout << p.F << " " << S << endl;
if (p.F == 0) return S;
else return (ex - stx + 1) * (ey - sty + 1) - S;
}
int get_ans(int r, int n)
{
int S = n * n;
int kx = (n + 1) / 2;
int k1 = kx * kx;
kx = n / 2;
k1 += kx * kx;
k1 *= r * r;
int k2 = S - k1;
int v1 = 0, v2 = 0;
for(int i = 0; i < m; i++)
{
int pl = (l2[i] - l1[i] + 1) * (r2[i] - r1[i] + 1);
int c1 = solve(r, l1[i], r1[i], l2[i], r2[i], 1);
int c2 = solve(r, l1[i], r1[i], l2[i], r2[i], 0);
v1 += c1;
k1 -= (pl - c1);
v2 += c2;
k2 -= (pl - c2);
}
return min(v1 + k1, v2 + k2);
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
3832 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 |
43 ms |
3832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
