Submission #893015

#	Time	Username	Problem	Language	Result	Execution time	Memory
893015		vjudge1	Chessboard (IZhO18_chessboard)	C++17	100 / 100	910 ms	13652 KiB

chessboard

// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>

#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif

using namespace std ;
using ll = long long ;

#define int ll

bool isPrime(int x) {
    if (x < 2) return 0 ;
    for (int i = 2 ; i * i <= x ; i++) {
        if (x  % i == 0) {
            return 0 ;
        }
    }
    return 1 ;
}

struct Fenwick {
   vector<ll> t ;
   int n;
   Fenwick(int len) {
      n = len ;
      t.assign(n + 1, 0) ;
   }
   void upd(int i, ll x) {
      while (i <= n) {
         t[i] += x;
         i += (i & (-i)) ;
      }
   }
   ll get(int i) {
      ll sum = 0 ;
      while (i) {
         sum += t[i] ;
         i -= (i & (-i)) ;
      }
      return sum ;
   }
   ll get(int l, int r) {
      return get(r) - get(l - 1) ;
   }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(false) ;
    ll n, k ; cin >> n >> k ;
    struct rect {
        int x1, y1, x2, y2;
        void read() {
            cin >> x1 >> y1 >> x2 >> y2 ;
            x1-- , y1-- , x2-- , y2-- ;
        }
    };
    vector<rect> a(k) ;
    for (int i = 0 ; i < k ; i++) a[i].read() ;
    vector<int> d;
    for (int i = 1 ; i * i <= n ; i++) {
        if (n % i) continue ;
        d.push_back(i) ;
        if (n / i != i) d.push_back(n / i) ;
    }
    auto calc = [&](ll del) -> ll{
        vector<vector<ll>> cnt(del, vector<ll>(2, 0)) ;
        int block = n / del ;
        vector<Fenwick> f(2, Fenwick(n + 2)) ;
        for (int i = 0 ; i < k ; i++) {
            int x1 = a[i].x1 , y1 = a[i].y1 , x2 = a[i].x2, y2 = a[i].y2 ;
            ll leny = (y2 - y1 + 1) ;
            ll lenx = (x2 - x1 + 1) ;
            ll bL = y1 / block , bR = y2 / block ;
            ll even = 0 , odd = 0 ;
            if (bL == bR) {
                if (bL & 1) {
                    odd += leny;
                } else {
                    even += leny ;
                }
            } else {
                ll ost = bR - bL - 1 ;
                if (ost > 0) {
                    if ((bL + 1) & 1) {
                        even += (ost / 2) * block ;
                        odd += (ost + 1) / 2 * block ;
                    } else {
                        even += (ost + 1) / 2 * block ;
                        odd += (ost / 2) * block ;
                    }
                }
                ll L = y1, R = (bL + 1) * block - 1 ;
                ll LN = (R - L + 1) ;
                if (bL & 1) {
                    odd += LN ;
                } else {
                    even += LN ;
                }
                L = bR * block , R = y2 ;
                LN = (R - L + 1) ;
                if (bR & 1) {
                    odd += LN ;
                } else {
                    even += LN ;
                }
            }
            dbg(even , odd) ;
            f[0].upd(x1 + 1, even) ;
            f[0].upd(x2 + 2, -even) ;
            f[1].upd(x1 + 1, odd) ;
            f[1].upd(x2 + 2, -odd) ;
        }
        for (int i = 1 ; i <= n ; i++) {
            dbg(f[0].get(i), f[1].get(i)) ;
            cnt[(i - 1) / block][0] += f[0].get(i) ;
            cnt[(i - 1) / block][1] += f[1].get(i) ;
        }
        dbg(del, cnt) ;
        ll ret = 0 , sum = 0 ;
        for (int i = 0 ; i < del ; i++) {
//            for (int j = 0 ; j < del ; j++) {
                if (i % 2 == 0) {
                    ll c = ((del + 1) / 2) * (block * block) ;
                    ll cur = c - cnt[i][0] + cnt[i][1] ;
                    sum += cur ;
                } else {
                    ll c = (del / 2) * (block * block) ;
                    ll cur = c - cnt[i][1] + cnt[i][0] ;
                    sum += cur ;
                }
//            }
        }
        ret = sum ;
        sum = 0 ;
        for (int i = 0 ; i < del ; i++) {
//            for (int j = 0 ; j < del ; j++) {
                if (i % 2 != 0) {
                    ll c = ((del + 1) / 2) * (block * block) ;
                    ll cur = c - cnt[i][0] + cnt[i][1] ;
                    sum += cur ;
                } else {
                    ll c = (del / 2) * (block * block) ;
                    ll cur = c - cnt[i][1] + cnt[i][0] ;
                    sum += cur ;
                }
//            }
        }
        ret = min(ret, sum) ;
        return ret ;
    };
    ll ret = LLONG_MAX ;
    for (int i : d) {
        if (i > 1) {
            ret = min(ret, calc(i)) ;
        }
    }
    cout << ret ;
    return 0 ;
}

// 希望白银

Compilation message (stderr)

chessboard.cpp: In lambda function:
chessboard.cpp:8:19: warning: statement has no effect [-Wunused-value]
    8 | #define dbg(x...) 0
      |                   ^
chessboard.cpp:112:13: note: in expansion of macro 'dbg'
  112 |             dbg(even , odd) ;
      |             ^~~
chessboard.cpp:77:16: warning: unused variable 'lenx' [-Wunused-variable]
   77 |             ll lenx = (x2 - x1 + 1) ;
      |                ^~~~
chessboard.cpp:8:19: warning: statement has no effect [-Wunused-value]
    8 | #define dbg(x...) 0
      |                   ^
chessboard.cpp:119:13: note: in expansion of macro 'dbg'
  119 |             dbg(f[0].get(i), f[1].get(i)) ;
      |             ^~~
chessboard.cpp:8:19: warning: statement has no effect [-Wunused-value]
    8 | #define dbg(x...) 0
      |                   ^
chessboard.cpp:123:9: note: in expansion of macro 'dbg'
  123 |         dbg(del, cnt) ;
      |         ^~~

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