#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> iiii;
const int maxn=1e5+5;
int n,k;
iiii black[maxn];
vector<int> divisors;
pair<ll,ll> calc(int d, iiii x) {
int cnt_col_0=0;
int cnt_col_1=0;
int cnt_row_0=0;
int cnt_row_1=0;
int l_col=x.fi.se/d;
int r_col=x.se.se/d;
if(l_col==r_col) {
if(l_col%2) cnt_col_1=r_col-l_col+1;
else cnt_col_0=r_col-l_col+1;
}
else {
int rem_l_col=d-x.fi.se%d;
int rem_r_col=x.se.se%d+1;
//cout<<"rem col l r "<<rem_l_col<<" "<<rem_r_col<<endl;
if(l_col&1) cnt_col_1+=rem_l_col;
else cnt_col_0+=rem_l_col;
if(r_col&1) cnt_col_1+=rem_r_col;
else cnt_col_0+=rem_r_col;
}
//cout<<"cnt_col 0 1 "<<cnt_col_0<<" "<<cnt_col_1<<endl;
l_col++;
r_col--;
if(l_col<=r_col) {
int diff=(r_col-l_col+1);
cnt_col_0+=diff*d/2;
cnt_col_1+=diff*d/2;
if(diff&1) {
if(l_col&1) cnt_col_1+=d;
else cnt_col_0+=d;
}
}
//cout<<"cnt_col 0 1 "<<cnt_col_0<<" "<<cnt_col_1<<endl;
int l_row=x.fi.fi/d;
int r_row=x.se.fi/d;
if(l_row==r_row) {
if(l_row%2) cnt_row_1=r_row-l_row+1;
else cnt_row_0=r_row-l_row+1;
}
else {
int rem_l_row=d-x.fi.fi%d;
int rem_r_row=x.se.fi%d+1;
if(l_row&1) cnt_row_1+=rem_l_row;
else cnt_row_0+=rem_l_row;
if(r_row&1) cnt_row_1+=rem_r_row;
else cnt_row_0+=rem_r_row;
}
//cout<<"cnt_row 0 1 "<<cnt_row_0<<" "<<cnt_row_1<<endl;
l_row++;
r_row--;
if(l_row<=r_row) {
int diff=(r_row-l_row+1);
cnt_row_0+=diff*d/2;
cnt_row_1+=diff*d/2;
if(diff&1) {
if(l_row&1) cnt_row_1+=d;
else cnt_row_0+=d;
}
}
//cout<<"cnt_row 0 1 "<<cnt_row_0<<" "<<cnt_row_1<<endl;
ll a0=1ll*cnt_col_0*cnt_row_0+1ll*cnt_col_1*cnt_row_1;
ll a1=1ll*cnt_col_0*cnt_row_1+1ll*cnt_col_1*cnt_row_0;
//cout<<"a0 a1 = "<<a0<<" "<<a1<<endl;
return make_pair(a0,a1);
}
ll solve(ll a0, ll a1, int d) {
int t=n/d;
ll ans=n*n;
//cout<<"solve "<<a0<<" "<<a1<<" "<<d<<endl;
if(t&1) {
ll c0=1ll*t*t/2+1;
ll c1=1ll*t*t/2+1;
c0*=1ll*d*d;
c1*=1ll*d*d;
ans=min(a0+c1-a1,a1+c0-a0);
swap(c0,c1);
ans=min(ans,a0+c1-a1);
ans=min(ans,a1+c0-a0);
return ans;
}
else {
ll c0=1ll*t*t/2;
ll c1=1ll*t*t/2;
c0*=1ll*d*d;
c1*=1ll*d*d;
return min(a0+c1-a1,a1+c0-a0);
}
}
signed main() {
cin>>n>>k;
for(int i=1 ; i<=k ; i++) {
cin>>black[i].fi.fi>>black[i].fi.se>>black[i].se.fi>>black[i].se.se;
black[i].fi.fi--; black[i].fi.se--;
black[i].se.fi--; black[i].se.se--;
}
for(int i=1 ; i<n ; i++) {
if(n%i==0) {
divisors.push_back(i);
}
}
ll ans=n*n;
for(int u: divisors) {
//cout<<"u = "<<u<<endl;
ll a0=0;
ll a1=0;
for(int i=1 ; i<=k ; i++) {
pair<ll,ll> tmp=calc(u,black[i]);
a0+=tmp.fi;
a1+=tmp.se;
}
ans=min(ans,solve(a0,a1,u));
}
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
1208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
1208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
