Submission #1143724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143724		imarn	Chessboard (IZhO18_chessboard)	C++20	39 / 100	45 ms	2496 KiB

chessboard

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=4e5+5;
struct square{
    int x1,y1,x2,y2;
};vector<square>sq;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=0;i<q;i++){
        square r;cin>>r.x1>>r.y1>>r.x2>>r.y2;
        sq.pb(r);
    }ll ans=1e16;
    for(int i=1;i<n;i++){
        if(n%i!=0)continue;
        int k=n/i;
        if(1){
            ll rs1,rs2;
            if(k&1){
                rs1=(k*k+1)/2*i*i;
                rs2=(k*k)/2*i*i;
            }
            else {
                rs1=k*k/2*i*i;
                rs2=rs1;
            }
            for(auto [x1,y1,x2,y2]:sq){
                    x1--,x2--,y1--,y2--;
                    int lx=x1/i+1,rx=x2/i-1,ly=y1/i+1,ry=y2/i-1;
                    if(lx<=rx&&ly<=ry){
                        if(((rx-lx+1)&1)&&((ry-ly+1)&1)){
                            if((lx&1)==(ly&1))rs1-=i*i,rs2+=i*i;
                            else rs1+=i*i,rs2-=i*i;
                        }
                    }lx--,rx++,ly--,ry++;
                    if(lx==rx&&ly==ry){
                        if((lx&1)==(ly&1))rs1-=(x2-x1+1)*(y2-y1+1),rs2+=(x2-x1+1)*(y2-y1+1);
                        else rs1+=(x2-x1+1)*(y2-y1+1),rs2-=(x2-x1+1)*(y2-y1+1);
                    }
                    else if(lx==rx&&ly<ry){
                        if((lx&1)==(ly&1))rs1-=((ly+1)*i-y1)*(x2-x1+1),rs2+=((ly+1)*i-y1)*(x2-x1+1);
                        else rs1+=((ly+1)*i-y1)*(x2-x1+1),rs2-=((ly+1)*i-y1)*(x2-x1+1);
                        if((lx&1)==(ry&1))rs1-=(y2-(ry)*i+1)*(x2-x1+1),rs2+=(y2-(ry)*i+1)*(x2-x1+1);
                        else rs1+=(y2-(ry)*i+1)*(x2-x1+1),rs2-=(y2-(ry)*i+1)*(x2-x1+1);
                        ly++,ry--;
                        if(ly<=ry){
                            if((ry-ly+1)&1){
                                if((lx&1)==(ly&1))rs1-=i*(x2-x1+1),rs2+=(x2-x1+1)*i;
                                else rs1+=i*(x2-x1+1),rs2-=(x2-x1+1)*i;
                            }
                        }ly--,ry++;
                    }
                    else if (lx<rx&&ly==ry){
                        if((lx&1)==(ly&1))rs1-=(y2-y1+1)*((lx+1)*i-x1),rs2+=(y2-y1+1)*((lx+1)*i-x1);
                        else rs1+=(y2-y1+1)*((lx+1)*i-x1),rs2-=(y2-y1+1)*((lx+1)*i-x1);
                        if((rx&1)==(ly&1))rs1-=(y2-y1+1)*(x2-(rx*i)+1),rs2+=(y2-y1+1)*(x2-(rx*i)+1);
                        else rs1+=(y2-y1+1)*(x2-(rx*i)+1),rs2-=(y2-y1+1)*(x2-(rx*i)+1);
                        lx++,rx--;
                        if(lx<=rx){
                            if((rx-lx+1)&1){
                                if((lx&1)==(ly&1))rs1-=i*(y2-y1+1),rs2+=i*(y2-y1+1);
                                else rs1+=i*(y2-y1+1),rs2-=i*(y2-y1+1);
                            }
                        }lx--,rx++;
                    }
                    else {
                        if((lx&1)==(ly&1))rs1-=(i*(lx+1)-x1)*(i*(ly+1)-y1),rs2+=(i*(lx+1)-x1)*(i*(ly+1)-y1);
                        else rs1+=(i*(lx+1)-x1)*(i*(ly+1)-y1),rs2-=(i*(lx+1)-x1)*(i*(ly+1)-y1);
                        if((lx&1)==(ry&1))rs1-=(i*(lx+1)-x1)*(y2-(ry*i)+1),rs2+=(i*(lx+1)-x1)*(y2-(ry*i)+1);
                        else rs1+=(i*(lx+1)-x1)*(y2-(ry*i)+1),rs2-=(i*(lx+1)-x1)*(y2-(ry*i)+1);
                        if((rx&1)==(ly&1))rs1-=(x2-(rx*i)+1)*(i*(ly+1)-y1),rs2+=(x2-(rx*i)+1)*(i*(ly+1)-y1);
                        else rs1+=(x2-(rx*i)+1)*(i*(ly+1)-y1),rs2-=(x2-(rx*i)+1)*(i*(ly+1)-y1);
                        if((rx&1)==(ry&1))rs1-=(x2-(rx*i)+1)*(y2-(ry*i)+1),rs2+=(x2-(rx*i)+1)*(y2-(ry*i)+1);
                        else rs1+=(x2-(rx*i)+1)*(y2-(ry*i)+1),rs2-=(x2-(rx*i)+1)*(y2-(ry*i)+1);
                        lx++,rx--;
                        if(lx<=rx){
                            if((rx-lx+1)&1){
                                if((lx&1)==(ly&1))rs1-=i*(i*(ly+1)-y1),rs2+=i*(i*(ly+1)-y1);
                                else rs1+=i*(i*(ly+1)-y1),rs2-=i*(i*(ly+1)-y1);
                                if((lx&1)==(ry&1))rs1-=i*(y2-(ry*i)+1),rs2+=i*(y2-(ry*i)+1);
                                else rs1+=i*(y2-(ry*i)+1),rs2-=i*(y2-(ry*i)+1);
                            }
                        }lx--,rx++;ly++,ry--;
                        if(ly<=ry){
                            if((ry-ly+1)&1){
                                if((lx&1)==(ly&1))rs1-=i*(i*(lx+1)-x1),rs2+=i*(i*(lx+1)-x1);
                                else rs1+=i*(i*(lx+1)-x1),rs2-=i*(i*(lx+1)-x1);
                                if((rx&1)==(ly&1))rs1-=i*(x2-(rx*i)+1),rs2+=i*(x2-(rx*i)+1);
                                else rs1+=i*(x2-(rx*i)+1),rs2-=i*(x2-(rx*i)+1);
                            }
                        }
                    }
            }ans=min({ans,rs1,rs2});
        }
    }cout<<ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30