oj.uz

Submission #893007

# Submission time Handle Problem Language Result Execution time Memory
893007 2023-12-26T10:14:28 Z vjudge1 Chessboard (IZhO18_chessboard) C++17
8 / 100
 23 ms 7260 KB 
// 以上帝的名义
// 候选硕士
#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 ;
        }
    };
    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 + 1, 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 - 1) / block , bR = (y2 - 1) / block ;
            ll ost = bR - bL - 1 ;
            ll even = 0 , odd = 0 ;
            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 ;
                }
            }
            for (int j = y1 - 1 ; j < y2 && j % block != 0 ; j++) {
                if ((j / block) & 1) {
                    odd++ ;
                } else {
                    even++ ;
                }
            }
            for (int j = (bR * block + block) ; j < y2 ; j++) {
                if ((j / block) & 1) {
                    odd++ ;
                } else {
                    even++ ;
                }
            }
            f[0].upd(x1, even) ;
            f[0].upd(x2 + 1, -even) ;
            f[1].upd(x1, odd) ;
            f[1].upd(x2 + 1, -odd) ;
        }
        for (int i = 1 ; i <= n ; i++) {
//            dbg(f[0].get(i), f[1].get(i)) ;
            cnt[(i - 1) / block][1] += f[0].get(i) ;
            cnt[(i - 1) / block][0] += 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

chessboard.cpp: In lambda function:
chessboard.cpp:75:16: warning: unused variable 'leny' [-Wunused-variable]
   75 |             ll leny = (y2 - y1 + 1) ;
      |                ^~~~
chessboard.cpp:76:16: warning: unused variable 'lenx' [-Wunused-variable]
   76 |             ll lenx = (x2 - x1 + 1) ;
      |                ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 7260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 7260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 23 ms 7260 KB Output isn't correct
10 Halted 0 ms 0 KB -