#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <cstring>
#include <array>
#include <bitset>
#include <cassert>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
array < int, 4 > l[maxn];
ll n, k;
inline ll dodaj(ll val, int br, bool p){
if((br&1 && p) || (!(br&1) && !p)){
return val;
}
return 0;
}
bool stima(int br, bool p){
return (br&1 && p) || (!(br&1) && !p);
}
ll probaj(ll val, bool p){
ll br=0;
ll x1, y1, x2, y2;
ll pocx, pocy, krajx, krajy;
ll cor1, cor2, cor3, cor4;
for(int i=0; i<k; i++){
x1=l[i][0];
y1=l[i][1];
x2=l[i][2];
y2=l[i][3];
pocx=x1/val;
pocy=y1/val;
krajx=x2/val;
krajy=y2/val;
if(pocx==krajx && pocy==krajy){
// cout << "izi!" << endl;
br+=dodaj((x2-x1+1)*(y2-y1+1), pocx+pocy, p);
}
else if(pocx==krajx){
// cout << "tu sam!" << endl;
cor1=x1;
cor2=y1;
cor3=min(x2, (pocx+1)*val-1);
cor4=min(y2, (pocy+1)*val-1);
// cout << cor1 << ' ' << cor2 << ' ' << cor3 << ' ' << cor4 << endl;
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);
cor1=max(x1, krajx*val);//
cor2=max(y1, krajy*val);//fixaj svugdje! bilo je poc
cor3=x2;
cor4=y2;
// cout << cor1 << ' ' << cor2 << ' ' << cor3 << ' ' << cor4 << endl;
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+krajy, p); //fixaj i ovo
pocy++;
krajy--;
if(pocy>krajy){
continue;
}
cor1=x1;
cor2=pocy*val;
cor3=x2;
cor4=(pocy+1)*val-1;
// cout << cor1 << ' ' << cor2 << ' ' << cor3 << ' ' << cor4 << endl;
// cout << pocy << ' ' << krajy << endl;
if(stima(pocx+pocy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajy-pocy+2)/2;
}
else{
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajy-pocy+1)/2;
}
}
else if(pocy==krajy){
// cout << "ovdje!" << endl;
cor1=x1;
cor2=y1;
cor3=min(x2, (pocx+1)*val-1);
cor4=min(y2, (pocy+1)*val-1);
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);
cor1=max(x1, krajx*val);
cor2=max(y1, krajy*val);
cor3=x2;
cor4=y2;
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+krajy, p);
pocx++;
krajx--;
if(pocx>krajx){
continue;
}
cor1=pocx*val;
cor2=y1;
cor3=(pocx+1)*val-1;
cor4=y2;
if(stima(pocx+pocy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajx-pocx+2)/2;
}
else{
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajx-pocx+1)/2;
}
}
else{
// cout << "kunito!" << endl;
cor1=x1;
cor2=y1;
cor3=min(x2, (pocx+1)*val-1);
cor4=min(y2, (pocy+1)*val-1);
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);
cor1=max(x1, krajx*val);
cor2=max(y1, krajy*val);
cor3=x2;
cor4=y2;
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+krajy, p);
cor1=x1;
cor2=max(y1, krajy*val);
cor3=min(x2, (pocx+1)*val-1);
cor4=y2;
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+krajy, p);
cor1=max(x1, krajx*val);
cor2=y1;
cor3=x2;
cor4=min(y2, (pocy+1)*val-1);
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+pocy, p);
pocx++;
krajx--;
if(krajx>=pocx){
cor1=pocx*val;
cor2=y1;
cor3=(pocx+1)*val-1;
cor4=(pocy+1)*val-1;
if(stima(pocx+pocy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajx-pocx+2)/2;
}
else{
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajx-pocx+1)/2;
}
cor2=krajy*val;
cor4=y2;
if(stima(pocx+krajy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajx-pocx+2)/2;
}
else{
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajx-pocx+1)/2;
}
}
pocx--;
krajx++;
pocy++;
krajy--;
if(krajy>=pocy){
cor1=x1;
cor2=pocy*val;
cor3=(pocx+1)*val-1;
cor4=(pocy+1)*val-1;
if(stima(pocx+pocy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajy-pocy+2)/2;
}
else{
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajy-pocy+1)/2;
}
cor1=krajx*val;
cor3=x2;
if(stima(krajx+pocy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajy-pocy+2)/2;
}
else{
br+=(cor3-cor1+1)*(cor4-cor2+1)*(krajy-pocy+1)/2;
}
}
pocy--;
krajy++;
if(((pocx+pocy)&1 && p) || (!((pocx+pocy)&1) && !p)){
br+=((krajx-pocx-1)*(krajy-pocy-1)+1)/2*val*val;
}
else{
br+=(krajx-pocx-1)*(krajy-pocy-1)/2*val*val;
}
}
}
// cout << br << endl;
return br;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
ll uk=0;
int a, b, c, d;
// cout << "proso" << endl;
for(int i=0; i<k; i++){
// cout << "uso" << endl;
cin >> a >> b >> c >> d;
a--;
b--;
c--;
d--;
uk+=(ll)(c-a+1)*(d-b+1);
l[i]={a, b, c, d};
}
ll sol=1e18;
ll br1, br2;
ll crno, bijelo;
for(ll i=1; i*i<=n; i++){
// cout << i << endl;
if(n%i==0){
br1=probaj(i, 0);
br2=probaj(i, 1);
crno=((n/i)*(n/i)+1)/2*i*i;
bijelo=(n/i)*(n/i)/2*i*i;
// cout << "boje " << bijelo << ' ' << crno << endl;
// cout << "brojevi " << br1 << ' ' << br2 << endl;
sol=min(sol, crno-br1+uk-br1);
swap(crno, bijelo);
sol=min(sol, crno-br2+uk-br2);
if(i!=1 && i*i!=n){
br1=probaj(n/i, 0);
br2=probaj(n/i, 1);
crno=(i*i+1)/2*(n/i)*(n/i);
bijelo=i*i/2*(n/i)*(n/i);
sol=min(sol, crno-br1+uk-br1);
swap(crno, bijelo);
sol=min(sol, crno-br2+uk-br2);
}
}
}
cout << sol << '\n';
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 |
376 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 |
27 ms |
1260 KB |
Output is correct |
2 |
Correct |
8 ms |
620 KB |
Output is correct |
3 |
Correct |
17 ms |
1004 KB |
Output is correct |
4 |
Correct |
19 ms |
1004 KB |
Output is correct |
5 |
Correct |
23 ms |
1132 KB |
Output is correct |
6 |
Correct |
15 ms |
876 KB |
Output is correct |
7 |
Correct |
4 ms |
492 KB |
Output is correct |
8 |
Correct |
15 ms |
876 KB |
Output is correct |
9 |
Correct |
39 ms |
1772 KB |
Output is correct |
10 |
Correct |
23 ms |
1132 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 |
2 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 |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
364 KB |
Output is correct |
14 |
Correct |
2 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
384 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 |
2 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 |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
364 KB |
Output is correct |
14 |
Correct |
2 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
14 ms |
748 KB |
Output is correct |
17 |
Correct |
31 ms |
1644 KB |
Output is correct |
18 |
Correct |
53 ms |
1920 KB |
Output is correct |
19 |
Correct |
142 ms |
1772 KB |
Output is correct |
20 |
Correct |
157 ms |
2028 KB |
Output is correct |
21 |
Correct |
29 ms |
1644 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
28 ms |
1004 KB |
Output is correct |
24 |
Correct |
41 ms |
1772 KB |
Output is correct |
25 |
Correct |
6 ms |
492 KB |
Output is correct |
26 |
Correct |
26 ms |
1260 KB |
Output is correct |
27 |
Correct |
38 ms |
1388 KB |
Output is correct |
28 |
Correct |
52 ms |
1772 KB |
Output is correct |
29 |
Correct |
13 ms |
876 KB |
Output is correct |
30 |
Correct |
2 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
1260 KB |
Output is correct |
2 |
Correct |
8 ms |
620 KB |
Output is correct |
3 |
Correct |
17 ms |
1004 KB |
Output is correct |
4 |
Correct |
19 ms |
1004 KB |
Output is correct |
5 |
Correct |
23 ms |
1132 KB |
Output is correct |
6 |
Correct |
15 ms |
876 KB |
Output is correct |
7 |
Correct |
4 ms |
492 KB |
Output is correct |
8 |
Correct |
15 ms |
876 KB |
Output is correct |
9 |
Correct |
39 ms |
1772 KB |
Output is correct |
10 |
Correct |
23 ms |
1132 KB |
Output is correct |
11 |
Correct |
1 ms |
364 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 |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
2 ms |
364 KB |
Output is correct |
24 |
Correct |
2 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
14 ms |
748 KB |
Output is correct |
27 |
Correct |
31 ms |
1644 KB |
Output is correct |
28 |
Correct |
53 ms |
1920 KB |
Output is correct |
29 |
Correct |
142 ms |
1772 KB |
Output is correct |
30 |
Correct |
157 ms |
2028 KB |
Output is correct |
31 |
Correct |
29 ms |
1644 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
28 ms |
1004 KB |
Output is correct |
34 |
Correct |
41 ms |
1772 KB |
Output is correct |
35 |
Correct |
6 ms |
492 KB |
Output is correct |
36 |
Correct |
26 ms |
1260 KB |
Output is correct |
37 |
Correct |
38 ms |
1388 KB |
Output is correct |
38 |
Correct |
52 ms |
1772 KB |
Output is correct |
39 |
Correct |
13 ms |
876 KB |
Output is correct |
40 |
Correct |
2 ms |
364 KB |
Output is correct |
41 |
Correct |
133 ms |
1644 KB |
Output is correct |
42 |
Correct |
49 ms |
1772 KB |
Output is correct |
43 |
Correct |
78 ms |
1644 KB |
Output is correct |
44 |
Correct |
48 ms |
1772 KB |
Output is correct |
45 |
Correct |
42 ms |
1900 KB |
Output is correct |
46 |
Correct |
145 ms |
1900 KB |
Output is correct |
47 |
Correct |
36 ms |
1644 KB |
Output is correct |
48 |
Correct |
65 ms |
1664 KB |
Output is correct |
49 |
Correct |
45 ms |
1792 KB |
Output is correct |
50 |
Correct |
631 ms |
1900 KB |
Output is correct |
51 |
Correct |
676 ms |
1912 KB |
Output is correct |
52 |
Correct |
624 ms |
1900 KB |
Output is correct |
53 |
Correct |
666 ms |
1900 KB |
Output is correct |
54 |
Correct |
634 ms |
1900 KB |
Output is correct |
55 |
Correct |
697 ms |
2028 KB |
Output is correct |
56 |
Correct |
603 ms |
1744 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 |
376 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 |
27 ms |
1260 KB |
Output is correct |
10 |
Correct |
8 ms |
620 KB |
Output is correct |
11 |
Correct |
17 ms |
1004 KB |
Output is correct |
12 |
Correct |
19 ms |
1004 KB |
Output is correct |
13 |
Correct |
23 ms |
1132 KB |
Output is correct |
14 |
Correct |
15 ms |
876 KB |
Output is correct |
15 |
Correct |
4 ms |
492 KB |
Output is correct |
16 |
Correct |
15 ms |
876 KB |
Output is correct |
17 |
Correct |
39 ms |
1772 KB |
Output is correct |
18 |
Correct |
23 ms |
1132 KB |
Output is correct |
19 |
Correct |
1 ms |
364 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 |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
2 ms |
364 KB |
Output is correct |
32 |
Correct |
2 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
14 ms |
748 KB |
Output is correct |
35 |
Correct |
31 ms |
1644 KB |
Output is correct |
36 |
Correct |
53 ms |
1920 KB |
Output is correct |
37 |
Correct |
142 ms |
1772 KB |
Output is correct |
38 |
Correct |
157 ms |
2028 KB |
Output is correct |
39 |
Correct |
29 ms |
1644 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
41 |
Correct |
28 ms |
1004 KB |
Output is correct |
42 |
Correct |
41 ms |
1772 KB |
Output is correct |
43 |
Correct |
6 ms |
492 KB |
Output is correct |
44 |
Correct |
26 ms |
1260 KB |
Output is correct |
45 |
Correct |
38 ms |
1388 KB |
Output is correct |
46 |
Correct |
52 ms |
1772 KB |
Output is correct |
47 |
Correct |
13 ms |
876 KB |
Output is correct |
48 |
Correct |
2 ms |
364 KB |
Output is correct |
49 |
Correct |
133 ms |
1644 KB |
Output is correct |
50 |
Correct |
49 ms |
1772 KB |
Output is correct |
51 |
Correct |
78 ms |
1644 KB |
Output is correct |
52 |
Correct |
48 ms |
1772 KB |
Output is correct |
53 |
Correct |
42 ms |
1900 KB |
Output is correct |
54 |
Correct |
145 ms |
1900 KB |
Output is correct |
55 |
Correct |
36 ms |
1644 KB |
Output is correct |
56 |
Correct |
65 ms |
1664 KB |
Output is correct |
57 |
Correct |
45 ms |
1792 KB |
Output is correct |
58 |
Correct |
631 ms |
1900 KB |
Output is correct |
59 |
Correct |
676 ms |
1912 KB |
Output is correct |
60 |
Correct |
624 ms |
1900 KB |
Output is correct |
61 |
Correct |
666 ms |
1900 KB |
Output is correct |
62 |
Correct |
634 ms |
1900 KB |
Output is correct |
63 |
Correct |
697 ms |
2028 KB |
Output is correct |
64 |
Correct |
603 ms |
1744 KB |
Output is correct |
65 |
Correct |
1 ms |
364 KB |
Output is correct |
66 |
Correct |
1 ms |
364 KB |
Output is correct |
67 |
Incorrect |
762 ms |
4204 KB |
Output isn't correct |
68 |
Halted |
0 ms |
0 KB |
- |