#include <bits/stdc++.h>
#define vc vector
#define nd node*
#define pnd pair<nd, nd>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vc<pll> vpll;
typedef vc<vll> vvll;
typedef vc<vpll> vvpll;
template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
ll operator()(const ll a, const ll b) {
return (a * b) % MOD;
}
};
template<typename T>
inline void sort(T &a) {
sort(a.begin(), a.end());
}
template<typename T>
inline void unique(T &a) {
a.resize(unique(a.begin(), a.end()) - a.begin());
}
template<typename T>
inline void reverse(T &a) {
reverse(a.begin(), a.end());
}
const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;
int s;
ll get(int x, int y, int c) {
return (ll)x * s * (y & 1) * ((c == 0) - (c == 1));
}
ll get(int x, int y) {
int a = x / s, b = y / s;
ll ans = 0;
if (((a & 1) + (b & 1)) >> 1) ans += (ll)s * s;
if ((a & 1) != (b & 1)) ans -= (ll)(x % s) * (y % s);
else ans += (ll)(x % s) * (y % s);
ans += get(x % s, b, a & 1);
ans += get(y % s, a, b & 1);
return ans;
}
int32_t main() {
cin.tie(nullptr)->ios_base::sync_with_stdio(false);
int n, k;
cin >> n >> k;
vc<vc<pair<int, int>>> tr(k, vc<pair<int, int>>(4));
for (auto &i: tr) {
int a, b, c, d;
cin >> a >> b >> c >> d;
i = {
{c, d},
{a - 1, d},
{c, b - 1},
{a - 1, b - 1}
};
}
ll ans = INF;
for (s = 1; s < n; ++s) {
if (n % s) continue;
ll sm = ((ll)n * n / s / s) / 2 * s * s;
for (auto &v : tr) {
sm += get(v[0].first, v[0].second) - get(v[1].first, v[1].second) -
get(v[2].first, v[2].second) + get(v[3].first, v[3].second);
}
ans = min(ans, min(sm, (ll)n * n - sm));
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
6120 KB |
Output is correct |
2 |
Correct |
8 ms |
1748 KB |
Output is correct |
3 |
Correct |
19 ms |
3992 KB |
Output is correct |
4 |
Correct |
19 ms |
4308 KB |
Output is correct |
5 |
Correct |
24 ms |
5452 KB |
Output is correct |
6 |
Correct |
16 ms |
3540 KB |
Output is correct |
7 |
Correct |
4 ms |
980 KB |
Output is correct |
8 |
Correct |
18 ms |
3552 KB |
Output is correct |
9 |
Correct |
40 ms |
8836 KB |
Output is correct |
10 |
Correct |
24 ms |
5008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
320 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
320 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
15 ms |
2636 KB |
Output is correct |
17 |
Correct |
32 ms |
7492 KB |
Output is correct |
18 |
Correct |
49 ms |
8780 KB |
Output is correct |
19 |
Correct |
161 ms |
7928 KB |
Output is correct |
20 |
Correct |
170 ms |
8796 KB |
Output is correct |
21 |
Correct |
30 ms |
7240 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
31 ms |
3920 KB |
Output is correct |
24 |
Correct |
43 ms |
8008 KB |
Output is correct |
25 |
Correct |
6 ms |
980 KB |
Output is correct |
26 |
Correct |
28 ms |
5204 KB |
Output is correct |
27 |
Correct |
39 ms |
6092 KB |
Output is correct |
28 |
Correct |
46 ms |
8556 KB |
Output is correct |
29 |
Correct |
13 ms |
3176 KB |
Output is correct |
30 |
Correct |
2 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
6120 KB |
Output is correct |
2 |
Correct |
8 ms |
1748 KB |
Output is correct |
3 |
Correct |
19 ms |
3992 KB |
Output is correct |
4 |
Correct |
19 ms |
4308 KB |
Output is correct |
5 |
Correct |
24 ms |
5452 KB |
Output is correct |
6 |
Correct |
16 ms |
3540 KB |
Output is correct |
7 |
Correct |
4 ms |
980 KB |
Output is correct |
8 |
Correct |
18 ms |
3552 KB |
Output is correct |
9 |
Correct |
40 ms |
8836 KB |
Output is correct |
10 |
Correct |
24 ms |
5008 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
320 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
2 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
15 ms |
2636 KB |
Output is correct |
27 |
Correct |
32 ms |
7492 KB |
Output is correct |
28 |
Correct |
49 ms |
8780 KB |
Output is correct |
29 |
Correct |
161 ms |
7928 KB |
Output is correct |
30 |
Correct |
170 ms |
8796 KB |
Output is correct |
31 |
Correct |
30 ms |
7240 KB |
Output is correct |
32 |
Correct |
2 ms |
340 KB |
Output is correct |
33 |
Correct |
31 ms |
3920 KB |
Output is correct |
34 |
Correct |
43 ms |
8008 KB |
Output is correct |
35 |
Correct |
6 ms |
980 KB |
Output is correct |
36 |
Correct |
28 ms |
5204 KB |
Output is correct |
37 |
Correct |
39 ms |
6092 KB |
Output is correct |
38 |
Correct |
46 ms |
8556 KB |
Output is correct |
39 |
Correct |
13 ms |
3176 KB |
Output is correct |
40 |
Correct |
2 ms |
460 KB |
Output is correct |
41 |
Correct |
142 ms |
8148 KB |
Output is correct |
42 |
Correct |
52 ms |
9108 KB |
Output is correct |
43 |
Correct |
79 ms |
8100 KB |
Output is correct |
44 |
Correct |
51 ms |
8892 KB |
Output is correct |
45 |
Correct |
43 ms |
9504 KB |
Output is correct |
46 |
Correct |
149 ms |
9024 KB |
Output is correct |
47 |
Correct |
38 ms |
8396 KB |
Output is correct |
48 |
Correct |
67 ms |
8468 KB |
Output is correct |
49 |
Correct |
46 ms |
8136 KB |
Output is correct |
50 |
Correct |
634 ms |
8752 KB |
Output is correct |
51 |
Correct |
661 ms |
9420 KB |
Output is correct |
52 |
Correct |
618 ms |
8780 KB |
Output is correct |
53 |
Correct |
677 ms |
9292 KB |
Output is correct |
54 |
Correct |
630 ms |
8604 KB |
Output is correct |
55 |
Correct |
683 ms |
9684 KB |
Output is correct |
56 |
Correct |
599 ms |
8424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
34 ms |
6120 KB |
Output is correct |
10 |
Correct |
8 ms |
1748 KB |
Output is correct |
11 |
Correct |
19 ms |
3992 KB |
Output is correct |
12 |
Correct |
19 ms |
4308 KB |
Output is correct |
13 |
Correct |
24 ms |
5452 KB |
Output is correct |
14 |
Correct |
16 ms |
3540 KB |
Output is correct |
15 |
Correct |
4 ms |
980 KB |
Output is correct |
16 |
Correct |
18 ms |
3552 KB |
Output is correct |
17 |
Correct |
40 ms |
8836 KB |
Output is correct |
18 |
Correct |
24 ms |
5008 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
320 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
2 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
15 ms |
2636 KB |
Output is correct |
35 |
Correct |
32 ms |
7492 KB |
Output is correct |
36 |
Correct |
49 ms |
8780 KB |
Output is correct |
37 |
Correct |
161 ms |
7928 KB |
Output is correct |
38 |
Correct |
170 ms |
8796 KB |
Output is correct |
39 |
Correct |
30 ms |
7240 KB |
Output is correct |
40 |
Correct |
2 ms |
340 KB |
Output is correct |
41 |
Correct |
31 ms |
3920 KB |
Output is correct |
42 |
Correct |
43 ms |
8008 KB |
Output is correct |
43 |
Correct |
6 ms |
980 KB |
Output is correct |
44 |
Correct |
28 ms |
5204 KB |
Output is correct |
45 |
Correct |
39 ms |
6092 KB |
Output is correct |
46 |
Correct |
46 ms |
8556 KB |
Output is correct |
47 |
Correct |
13 ms |
3176 KB |
Output is correct |
48 |
Correct |
2 ms |
460 KB |
Output is correct |
49 |
Correct |
142 ms |
8148 KB |
Output is correct |
50 |
Correct |
52 ms |
9108 KB |
Output is correct |
51 |
Correct |
79 ms |
8100 KB |
Output is correct |
52 |
Correct |
51 ms |
8892 KB |
Output is correct |
53 |
Correct |
43 ms |
9504 KB |
Output is correct |
54 |
Correct |
149 ms |
9024 KB |
Output is correct |
55 |
Correct |
38 ms |
8396 KB |
Output is correct |
56 |
Correct |
67 ms |
8468 KB |
Output is correct |
57 |
Correct |
46 ms |
8136 KB |
Output is correct |
58 |
Correct |
634 ms |
8752 KB |
Output is correct |
59 |
Correct |
661 ms |
9420 KB |
Output is correct |
60 |
Correct |
618 ms |
8780 KB |
Output is correct |
61 |
Correct |
677 ms |
9292 KB |
Output is correct |
62 |
Correct |
630 ms |
8604 KB |
Output is correct |
63 |
Correct |
683 ms |
9684 KB |
Output is correct |
64 |
Correct |
599 ms |
8424 KB |
Output is correct |
65 |
Correct |
1 ms |
212 KB |
Output is correct |
66 |
Correct |
1 ms |
212 KB |
Output is correct |
67 |
Correct |
712 ms |
9056 KB |
Output is correct |
68 |
Correct |
763 ms |
9036 KB |
Output is correct |
69 |
Correct |
618 ms |
7884 KB |
Output is correct |
70 |
Correct |
705 ms |
8776 KB |
Output is correct |
71 |
Correct |
671 ms |
8588 KB |
Output is correct |
72 |
Correct |
694 ms |
8448 KB |
Output is correct |
73 |
Correct |
675 ms |
8212 KB |
Output is correct |
74 |
Correct |
737 ms |
9024 KB |
Output is correct |
75 |
Correct |
695 ms |
8520 KB |
Output is correct |
76 |
Correct |
735 ms |
9084 KB |
Output is correct |
77 |
Correct |
133 ms |
9532 KB |
Output is correct |
78 |
Correct |
53 ms |
8768 KB |
Output is correct |
79 |
Correct |
92 ms |
8176 KB |
Output is correct |
80 |
Correct |
102 ms |
8652 KB |
Output is correct |
81 |
Correct |
91 ms |
8012 KB |
Output is correct |
82 |
Correct |
80 ms |
9136 KB |
Output is correct |
83 |
Correct |
67 ms |
8384 KB |
Output is correct |
84 |
Correct |
440 ms |
9396 KB |
Output is correct |
85 |
Correct |
790 ms |
9612 KB |
Output is correct |
86 |
Correct |
2 ms |
212 KB |
Output is correct |
87 |
Correct |
1 ms |
212 KB |
Output is correct |
88 |
Correct |
776 ms |
9616 KB |
Output is correct |
89 |
Correct |
142 ms |
2004 KB |
Output is correct |
90 |
Correct |
1 ms |
212 KB |
Output is correct |