This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e5+6;
const ll INF=2e17;
ll emi_da(ll x,ll k)
{
ll t=(x-1)/k;
t/=2;
ll f=t*(2*k)+1;
return t*k+min(k,(x-f+1));
}
struct rect
{
ll x1,y1,x2,y2;
}r[MAXN];
ll calc_black(rect r1,int k)
{
ll t1=emi_da(r1.x1-1,k),t2=emi_da(r1.x2,k);
ll t=t2-t1;
ll h1=emi_da(r1.y1-1,k),h2=emi_da(r1.y2,k);
ll h=h2-h1;
return t*h+(r1.x2-r1.x1+1-t)*(r1.y2-r1.y1+1-h);
}
ll ans=INF;
int main()
{
ll n,k;
cin>>n>>k;
for(ll i=1;i<=k;i++)cin>>r[i].x1>>r[i].y1>>r[i].x2>>r[i].y2;
for(ll i=1;i<=n/2;i++)
{
//cout<<i<<":\n";
if(n%i==0)
{
ll s=((n/i)*(n/i)+1)/2*(i*i);
for(int j=1;j<=k;j++)
{
ll p=calc_black(r[j],i);
//cout<<j<<" "<<p<<endl;
s-=p;
s+=(r[j].x2-r[j].x1+1)*(r[j].y2-r[j].y1+1)-p;
}
//cout<<s<<endl;
ans=min(ans,s);
s=((n/i)*(n/i))/2*(i*i);
for(int j=1;j<=k;j++)
{
ll p=calc_black(r[j],i);
s-=(r[j].x2-r[j].x1+1)*(r[j].y2-r[j].y1+1)-p;
s+=p;
}
ans=min(ans,s);
//cout<<s<<endl;
}
}
cout<<ans<<endl;
return 0;
}
/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |