#include<bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
struct eventhelp{
long long t;
long long l, r;
long long val;
long long type;
};
void add_int(long long l, long long r, long long val, long long &cnti, long long &cntp){
long long pare, impare;
long long dst = r - l + 1;
pare = dst/2;
impare = dst/2;
if(dst%2 == 1){
if(l%2 == 0)
pare++;
else
impare++;
}
cnti += 1LL * impare * val;
cntp += 1LL * pare * val;
}
vector<eventhelp> ev;
long long ans = LLONG_MAX;
long long n;
bool cmpev(eventhelp a, eventhelp b){
if(a.t == b.t)
return a.type > b.type;
return a.t < b.t;
}
long long imp[N], pr[N];
void solve(long long len){
vector<eventhelp> evc = ev;
for(long long i=len; i<=n;i+=len){
evc.push_back({i, 0, 0, 0});
}
inplace_merge(evc.begin(), evc.begin() + ev.size(), evc.end(), cmpev);
long long sumi = 0, acti = 0, sump = 0, actp = 0;
for(auto e:evc){
if(e.type != 0){
long long fgroup = (e.l - 1)/len + 1;
long long lgroup = (e.r - 1)/len + 1;
if(fgroup + 1 <= lgroup - 1){
add_int(fgroup + 1, lgroup - 1, 1LL* e.val * len, sumi, sump);
add_int(fgroup + 1, lgroup - 1, 1LL* e.type * len, acti, actp);
}
if(fgroup != lgroup){
add_int(fgroup, fgroup, 1LL * e.val * (fgroup*len - e.l + 1), sumi, sump);
add_int(fgroup, fgroup, 1LL * e.type * (fgroup*len - e.l + 1), acti, actp);
add_int(lgroup, lgroup, 1LL * e.val * (e.r - (lgroup - 1)*len), sumi, sump);
add_int(lgroup, lgroup, 1LL * e.type * (e.r - (lgroup - 1)*len), acti, actp);
}
if(fgroup == lgroup){
add_int(fgroup, fgroup, 1LL * e.val * (e.r - e.l + 1), sumi, sump);
add_int(fgroup, fgroup, 1LL * e.type * (e.r - e.l + 1), acti, actp);
}
}
else{
long long csumi, csump;
csumi = sumi - acti * (n - e.t);
csump = sump - actp * (n - e.t);
imp[e.t/len] = csumi;
pr[e.t/len] =csump;
}
}
long long fans = 0, sans = 0;
for(long long i = 1; i<=n/len;i++){
long long ci, cp;
ci = imp[i] - imp[i-1];
cp = pr[i] - pr[i -1];
long long nrp = (n/len)/2, nri = n/len - nrp;
if(i %2 == 1){
fans += 1LL*len*len*nri - ci + cp;
sans += 1LL*len*len*nrp - cp + ci;
}
else{
sans += 1LL*len*len*nri - ci + cp;
fans += 1LL*len*len*nrp - cp + ci;
}
}
ans = min(ans, sans);
ans = min(ans, fans);
}
int main()
{
//freopen(".in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
long long k;
cin>>n>>k;
for(long long i=1;i<=k;i++){
long long x1, y1, x2, y2;
cin>>x1>>y1>>x2>>y2;
ev.push_back({x1, y1, y2, n - x1 + 1, 1});
ev.push_back({x2, y1, y2,-(n - x2), -1});
}
sort(ev.begin(), ev.end(), cmpev);
for(long long d = 1; d<n; d++){
if(n%d == 0)
solve(d);
}
cout<<ans;
return 0;
}
# |
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 |
Correct |
72 ms |
15572 KB |
Output is correct |
2 |
Correct |
19 ms |
4700 KB |
Output is correct |
3 |
Correct |
53 ms |
16336 KB |
Output is correct |
4 |
Correct |
46 ms |
11608 KB |
Output is correct |
5 |
Correct |
63 ms |
13872 KB |
Output is correct |
6 |
Correct |
45 ms |
10180 KB |
Output is correct |
7 |
Correct |
11 ms |
3620 KB |
Output is correct |
8 |
Correct |
44 ms |
10148 KB |
Output is correct |
9 |
Correct |
102 ms |
22076 KB |
Output is correct |
10 |
Correct |
58 ms |
12628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
2 ms |
668 KB |
Output is correct |
5 |
Correct |
1 ms |
620 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
620 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
2 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
2 ms |
620 KB |
Output is correct |
14 |
Correct |
2 ms |
668 KB |
Output is correct |
15 |
Correct |
1 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
2 ms |
668 KB |
Output is correct |
5 |
Correct |
1 ms |
620 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
620 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
2 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
2 ms |
620 KB |
Output is correct |
14 |
Correct |
2 ms |
668 KB |
Output is correct |
15 |
Correct |
1 ms |
620 KB |
Output is correct |
16 |
Correct |
35 ms |
7408 KB |
Output is correct |
17 |
Correct |
86 ms |
20828 KB |
Output is correct |
18 |
Correct |
136 ms |
24132 KB |
Output is correct |
19 |
Correct |
396 ms |
21664 KB |
Output is correct |
20 |
Correct |
452 ms |
24136 KB |
Output is correct |
21 |
Correct |
78 ms |
19908 KB |
Output is correct |
22 |
Correct |
1 ms |
620 KB |
Output is correct |
23 |
Correct |
77 ms |
10836 KB |
Output is correct |
24 |
Correct |
115 ms |
22012 KB |
Output is correct |
25 |
Correct |
15 ms |
2656 KB |
Output is correct |
26 |
Correct |
68 ms |
14164 KB |
Output is correct |
27 |
Correct |
102 ms |
16836 KB |
Output is correct |
28 |
Correct |
119 ms |
23368 KB |
Output is correct |
29 |
Correct |
34 ms |
8812 KB |
Output is correct |
30 |
Correct |
4 ms |
1192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
15572 KB |
Output is correct |
2 |
Correct |
19 ms |
4700 KB |
Output is correct |
3 |
Correct |
53 ms |
16336 KB |
Output is correct |
4 |
Correct |
46 ms |
11608 KB |
Output is correct |
5 |
Correct |
63 ms |
13872 KB |
Output is correct |
6 |
Correct |
45 ms |
10180 KB |
Output is correct |
7 |
Correct |
11 ms |
3620 KB |
Output is correct |
8 |
Correct |
44 ms |
10148 KB |
Output is correct |
9 |
Correct |
102 ms |
22076 KB |
Output is correct |
10 |
Correct |
58 ms |
12628 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
2 ms |
668 KB |
Output is correct |
15 |
Correct |
1 ms |
620 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
620 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
2 ms |
492 KB |
Output is correct |
22 |
Correct |
1 ms |
492 KB |
Output is correct |
23 |
Correct |
2 ms |
620 KB |
Output is correct |
24 |
Correct |
2 ms |
668 KB |
Output is correct |
25 |
Correct |
1 ms |
620 KB |
Output is correct |
26 |
Correct |
35 ms |
7408 KB |
Output is correct |
27 |
Correct |
86 ms |
20828 KB |
Output is correct |
28 |
Correct |
136 ms |
24132 KB |
Output is correct |
29 |
Correct |
396 ms |
21664 KB |
Output is correct |
30 |
Correct |
452 ms |
24136 KB |
Output is correct |
31 |
Correct |
78 ms |
19908 KB |
Output is correct |
32 |
Correct |
1 ms |
620 KB |
Output is correct |
33 |
Correct |
77 ms |
10836 KB |
Output is correct |
34 |
Correct |
115 ms |
22012 KB |
Output is correct |
35 |
Correct |
15 ms |
2656 KB |
Output is correct |
36 |
Correct |
68 ms |
14164 KB |
Output is correct |
37 |
Correct |
102 ms |
16836 KB |
Output is correct |
38 |
Correct |
119 ms |
23368 KB |
Output is correct |
39 |
Correct |
34 ms |
8812 KB |
Output is correct |
40 |
Correct |
4 ms |
1192 KB |
Output is correct |
41 |
Correct |
359 ms |
25840 KB |
Output is correct |
42 |
Correct |
137 ms |
24936 KB |
Output is correct |
43 |
Correct |
219 ms |
24472 KB |
Output is correct |
44 |
Correct |
135 ms |
26276 KB |
Output is correct |
45 |
Correct |
121 ms |
24040 KB |
Output is correct |
46 |
Correct |
406 ms |
27968 KB |
Output is correct |
47 |
Correct |
103 ms |
22052 KB |
Output is correct |
48 |
Correct |
183 ms |
23864 KB |
Output is correct |
49 |
Correct |
129 ms |
22672 KB |
Output is correct |
50 |
Correct |
1719 ms |
26740 KB |
Output is correct |
51 |
Correct |
1826 ms |
27996 KB |
Output is correct |
52 |
Correct |
1696 ms |
26580 KB |
Output is correct |
53 |
Correct |
1802 ms |
27944 KB |
Output is correct |
54 |
Correct |
1648 ms |
26340 KB |
Output is correct |
55 |
Correct |
1882 ms |
28792 KB |
Output is correct |
56 |
Correct |
1622 ms |
25680 KB |
Output is correct |
# |
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 |
Correct |
72 ms |
15572 KB |
Output is correct |
10 |
Correct |
19 ms |
4700 KB |
Output is correct |
11 |
Correct |
53 ms |
16336 KB |
Output is correct |
12 |
Correct |
46 ms |
11608 KB |
Output is correct |
13 |
Correct |
63 ms |
13872 KB |
Output is correct |
14 |
Correct |
45 ms |
10180 KB |
Output is correct |
15 |
Correct |
11 ms |
3620 KB |
Output is correct |
16 |
Correct |
44 ms |
10148 KB |
Output is correct |
17 |
Correct |
102 ms |
22076 KB |
Output is correct |
18 |
Correct |
58 ms |
12628 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
2 ms |
668 KB |
Output is correct |
23 |
Correct |
1 ms |
620 KB |
Output is correct |
24 |
Correct |
1 ms |
492 KB |
Output is correct |
25 |
Correct |
1 ms |
620 KB |
Output is correct |
26 |
Correct |
1 ms |
492 KB |
Output is correct |
27 |
Correct |
1 ms |
492 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
2 ms |
492 KB |
Output is correct |
30 |
Correct |
1 ms |
492 KB |
Output is correct |
31 |
Correct |
2 ms |
620 KB |
Output is correct |
32 |
Correct |
2 ms |
668 KB |
Output is correct |
33 |
Correct |
1 ms |
620 KB |
Output is correct |
34 |
Correct |
35 ms |
7408 KB |
Output is correct |
35 |
Correct |
86 ms |
20828 KB |
Output is correct |
36 |
Correct |
136 ms |
24132 KB |
Output is correct |
37 |
Correct |
396 ms |
21664 KB |
Output is correct |
38 |
Correct |
452 ms |
24136 KB |
Output is correct |
39 |
Correct |
78 ms |
19908 KB |
Output is correct |
40 |
Correct |
1 ms |
620 KB |
Output is correct |
41 |
Correct |
77 ms |
10836 KB |
Output is correct |
42 |
Correct |
115 ms |
22012 KB |
Output is correct |
43 |
Correct |
15 ms |
2656 KB |
Output is correct |
44 |
Correct |
68 ms |
14164 KB |
Output is correct |
45 |
Correct |
102 ms |
16836 KB |
Output is correct |
46 |
Correct |
119 ms |
23368 KB |
Output is correct |
47 |
Correct |
34 ms |
8812 KB |
Output is correct |
48 |
Correct |
4 ms |
1192 KB |
Output is correct |
49 |
Correct |
359 ms |
25840 KB |
Output is correct |
50 |
Correct |
137 ms |
24936 KB |
Output is correct |
51 |
Correct |
219 ms |
24472 KB |
Output is correct |
52 |
Correct |
135 ms |
26276 KB |
Output is correct |
53 |
Correct |
121 ms |
24040 KB |
Output is correct |
54 |
Correct |
406 ms |
27968 KB |
Output is correct |
55 |
Correct |
103 ms |
22052 KB |
Output is correct |
56 |
Correct |
183 ms |
23864 KB |
Output is correct |
57 |
Correct |
129 ms |
22672 KB |
Output is correct |
58 |
Correct |
1719 ms |
26740 KB |
Output is correct |
59 |
Correct |
1826 ms |
27996 KB |
Output is correct |
60 |
Correct |
1696 ms |
26580 KB |
Output is correct |
61 |
Correct |
1802 ms |
27944 KB |
Output is correct |
62 |
Correct |
1648 ms |
26340 KB |
Output is correct |
63 |
Correct |
1882 ms |
28792 KB |
Output is correct |
64 |
Correct |
1622 ms |
25680 KB |
Output is correct |
65 |
Correct |
1 ms |
364 KB |
Output is correct |
66 |
Correct |
1 ms |
364 KB |
Output is correct |
67 |
Correct |
1808 ms |
27232 KB |
Output is correct |
68 |
Correct |
1777 ms |
29072 KB |
Output is correct |
69 |
Correct |
1570 ms |
25860 KB |
Output is correct |
70 |
Correct |
1729 ms |
28276 KB |
Output is correct |
71 |
Correct |
1722 ms |
27844 KB |
Output is correct |
72 |
Correct |
1671 ms |
27408 KB |
Output is correct |
73 |
Correct |
1655 ms |
26896 KB |
Output is correct |
74 |
Correct |
1776 ms |
28904 KB |
Output is correct |
75 |
Correct |
1695 ms |
27636 KB |
Output is correct |
76 |
Correct |
1824 ms |
29360 KB |
Output is correct |
77 |
Correct |
324 ms |
31312 KB |
Output is correct |
78 |
Correct |
137 ms |
25512 KB |
Output is correct |
79 |
Correct |
227 ms |
27808 KB |
Output is correct |
80 |
Correct |
242 ms |
28868 KB |
Output is correct |
81 |
Correct |
221 ms |
25712 KB |
Output is correct |
82 |
Correct |
194 ms |
28964 KB |
Output is correct |
83 |
Correct |
163 ms |
28036 KB |
Output is correct |
84 |
Correct |
1088 ms |
30820 KB |
Output is correct |
85 |
Correct |
1877 ms |
30632 KB |
Output is correct |
86 |
Correct |
20 ms |
5828 KB |
Output is correct |
87 |
Correct |
18 ms |
5160 KB |
Output is correct |
88 |
Correct |
1883 ms |
30776 KB |
Output is correct |
89 |
Correct |
188 ms |
11128 KB |
Output is correct |
90 |
Correct |
19 ms |
5920 KB |
Output is correct |