#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define z return 0;
using namespace std;
const int N = 1e5 + 5, inf = 1e9 + 1; //
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int n, k;
cin >> n >> k;
int a[k], b[k], c[k], d[k];
for (int i = 0; i < k; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
ll ans = inf;
for (int l = 1; l < n; l++){
if (n % l) continue;
int l2 = n / l;
ll tmp = 1ll * l * l * (1ll * l2 * l2 / 2), tmp2 = tmp + 1ll * l * l * (l2 % 2);
swap(tmp, tmp2);
int d0[n + 1]{}, d1[n + 1]{}, pre[n + 1]{};
for (int i = 1; i <= n; i++){
pre[i] = pre[i - 1] + (i % (l * 2) > 0 and i % (l * 2) <= l);
}
for (int i = 0; i < k; i++){
int p = pre[c[i]] - pre[a[i] - 1], p2 = c[i] - a[i] + 1 - p;
d0[b[i]] += p;
d0[d[i] + 1] -= p;
d1[b[i]] += p2;
d1[d[i] + 1] -= p2;
}
ll pre0 = 0, pre1 = 0;
for (int i = 1; i <= n; i++){
pre0 += d0[i], pre1 += d1[i];
if (i % (l * 2) > 0 and i % (l * 2) <= l){
tmp += pre1 - pre0;
tmp2 += pre0 - pre1;
}
else{
tmp2 += pre1 - pre0;
tmp += pre0 - pre1;
}
}
ans = min({ans, tmp, tmp2});
}
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 |
364 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 |
Incorrect |
25 ms |
3564 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Incorrect |
1 ms |
236 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Incorrect |
1 ms |
236 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
3564 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
364 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 |
Incorrect |
25 ms |
3564 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |