Submission #1129496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129496		Gray	Chessboard (IZhO18_chessboard)	C++20	47 / 100	2094 ms	16452 KiB

chessboard

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

const ll INF = 2e18;
const ll MOD = 1e9+7;

struct segtree{
    struct node{
        ll on, off, upd;
    };
    vector<node> t;
    ll sz, rsz;
    void init(ll N){
        rsz=N; sz=N*4;
        t.resize(sz);
        gen(0, rsz-1, 1);
    }
    void gen(ll tl, ll tr, ll v){
        if (tl==tr){
            t[v] = {0, 1, 0};
        }else{
            ll tm = (tl+tr)/2;
            gen(tl, tm, v*2);
            gen(tm+1, tr, v*2+1);
            t[v].on=t[v].upd=0;
            t[v].off=t[v*2].off+t[v*2+1].off;
        }
    }
    void preprocess(ll tl, ll tr, ll v){
        if (tl!=tr) {
            t[v*2].upd+=t[v].upd; t[v*2+1].upd+=t[v].upd;
        }
        if (t[v].upd%2){
            swap(t[v].off, t[v].on);
        }
        t[v].upd=0;
    }
    void flip(ll tl, ll tr, ll v, ll l, ll r){
        preprocess(tl, tr, v);
        if (tl==l and tr==r){
            t[v].upd++;
            preprocess(tl, tr, v);
        }else if (l>r) return;
        else{
            ll tm = (tl+tr)/2;
            flip(tl, tm, v*2, l, min(r, tm));
            flip(tm+1, tr, v*2+1, max(l, tm+1), r);
            t[v].on=t[v*2].on+t[v*2+1].on;
            t[v].off=t[v*2].off+t[v*2+1].off;
        }
    }
    void flip(ll l, ll r){
        flip(0, rsz-1, 1, l, r);
    }
} tr;

ll n, k;
vector<vector<pair<ll, ll>>> upd;

ll check(ll x){
    tr.init(n);
    for (ll i=0; i<n; i++){
        if ((i/x)%2) tr.flip(i, i);
    }
    ll res=0;
    for (ll i=0; i<n; i++){
        if (i%x==0) tr.flip(0, n-1);
        for (auto ch:upd[i]){
            tr.flip(ch.ff, ch.ss);
        }
        res+=tr.t[1].on;
    }
    tr.init(n);
    for (ll i=0; i<n; i++){
        if ((i/x)%2==0) tr.flip(i, i);
    }
    ll res2=0;
    for (ll i=0; i<n; i++){
        if (i%x==0) tr.flip(0, n-1);
        for (auto ch:upd[i]){
            tr.flip(ch.ff, ch.ss);
        }
        res2+=tr.t[1].on;
    }
    // cout << x << ": " << res << " - " << res2 << ln;
    return min(res, res2);
}

void solve(){
    cin >> n >> k;
    upd.resize(n+1);
    for (ll i=0; i<k; i++){
        ll si, sj, ti, tj; cin >> si >> sj >> ti >> tj;
        si--; sj--; ti--; tj--;
        upd[sj].push_back({si, ti});
        upd[tj+1].push_back({si, ti});
    }
    ll res=INF;
    for (ll i=1; i*i<=n; i++){
        if (n%i==0){
            res=min(res, check(i));
            if (n/i<n) res=min(res, check(n/i));
        }
    }
    cout << res << ln;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = chrono::high_resolution_clock::now();
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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