Submission #153914

#	Time	Username	Problem	Language	Result	Execution time	Memory
153914		andrew	Chessboard (IZhO18_chessboard)	C++17	100 / 100	1481 ms	7416 KiB

chessboard

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T> void vout(T s){cout << s << endl;exit(0);}

struct rectangle{
    ll x1, y1, x2, y2;
};

vector <rectangle> b;

vector <ll> pref, pref1;

ll n, k;

ll f(ll len){
    ll kol = n / len;
    ll res = 0;
    ll S = 0, TrueS = 0;
    if(k){
        for(auto i : b){
            S += (i.x2 - i.x1 + 1) * (i.y2 - i.y1 + 1);
            ll old = TrueS;

            ll l = i.x1 / len + (i.x1 % len > 0), r = i.x2 / len + (i.x2 % len > 0);
            if(l == r){
                if(l % 2){
                    TrueS += (i.x2 - i.x1 + 1) * (pref[i.y2] - pref[i.y1 - 1]);
                }
                else{
                    TrueS += (i.x2 - i.x1 + 1) * (pref1[i.y2] - pref1[i.y1 - 1]);
                }
            }else{
                if(l % 2){
                    TrueS += (l * len + 1 - i.x1) * (pref[i.y2] - pref[i.y1 - 1]);
                }else{
                    TrueS += (l * len + 1 - i.x1) * (pref1[i.y2] - pref1[i.y1 - 1]);
                }

                if(r % 2){
                    TrueS += (i.x2 - len * (r - 1)) * (pref[i.y2] - pref[i.y1 - 1]);
                }else{
                    TrueS += (i.x2 - len * (r - 1)) * (pref1[i.y2] - pref1[i.y1 - 1]);
                }

                if(l + 1 < r){
                    ll ft = l + 1;
                    ll Kol = r - l - 1;
                    if(ft % 2){
                        TrueS += len * ((pref[i.y2] - pref[i.y1 - 1]) * ((Kol + 1) / 2) + (pref1[i.y2] - pref1[i.y1 - 1]) * (Kol / 2));
                    }else{
                        TrueS += len * ((pref1[i.y2] - pref1[i.y1 - 1]) * ((Kol + 1) / 2) + (pref[i.y2] - pref[i.y1 - 1]) * (Kol / 2));
                    }
                }
            }

        }
    }
    res += S - TrueS;
    res += len * pref[n] * ((kol + 1) / 2) + len * pref1[n] * (kol / 2) - TrueS;
    return res;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;

    pref.resize(n + 1);
    pref1.resize(n + 1);

    b.resize(k);

    for(int i = 0; i < k; i++)cin >> b[i].x1 >> b[i].y1 >> b[i].x2 >> b[i].y2;

    ll ans = 1e18;

    for(int i = 1; i < n; i++)if(n % i == 0){

        //firstComb


        for(int j = 1; j <= n; j++)pref[j] = 0;
        for(int j = 1; j <= n; j++)pref1[j] = 1;

        ll uk = 1;
        while(uk <= n){
            for(int j = 1; j <= i; j++)pref[uk + j - 1] = 1;
            uk += 2 * i;
        }

        uk = 1;
        while(uk <= n){
            for(int j = 1; j <= i; j++)pref1[uk + j - 1] = 0;
            uk += 2 * i;
        }

        for(int j = 1; j <= n; j++)pref[j] += pref[j - 1];
        for(int j = 1; j <= n; j++)pref1[j] += pref1[j - 1];

        ans = min(ans, f(i));

        //secondComb

        for(int j = 1; j <= n; j++)pref[j] = 1;
        for(int j = 1; j <= n; j++)pref1[j] = 0;

        uk = 1;
        while(uk <= n){
            for(int j = 1; j <= i; j++)pref[uk + j - 1] = 0;
            uk += 2 * i;
        }

        uk = 1;
        while(uk <= n){
            for(int j = 1; j <= i; j++)pref1[uk + j - 1] = 1;
            uk += 2 * i;
        }

        for(int j = 1; j <= n; j++)pref[j] += pref[j - 1];
        for(int j = 1; j <= n; j++)pref1[j] += pref1[j - 1];

        ans = min(ans, f(i));
    }

    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'll f(ll)':
chessboard.cpp:50:16: warning: unused variable 'old' [-Wunused-variable]
             ll old = TrueS;
                ^~~

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