제출 #878924

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878924		TheSahib	Chessboard (IZhO18_chessboard)	C++14	47 / 100	2078 ms	8788 KiB

chessboard

#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>

using namespace std;

const int MAX = 1e5 + 5;
const ll oo = 1e15;

int tree[MAX * 4], lazy[MAX * 4];

void build(int node, int l, int r, int k){
    lazy[node] = 0;
    if(l == r){
        tree[node] = ((l - 1) / k) & 1;
        return;
    }
    int mid = (l + r) / 2;
    build(node * 2, l, mid, k);
    build(node * 2 + 1, mid + 1, r, k);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void relax(int node, int l, int r){
    if(!lazy[node]) return;
    tree[node] = (r - l + 1) - tree[node];
    if(l != r){
        lazy[node * 2] ^= 1;
        lazy[node * 2 + 1] ^= 1;
    }
    lazy[node] = 0;
    return;
}

void update(int node, int l, int r, int ql, int qr){
    relax(node, l, r);
    if(ql > r || qr < l) return;
    if(ql <= l && r <= qr){
        lazy[node] ^= 1;
        relax(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(node * 2, l, mid, ql, qr);
    update(node * 2 + 1, mid + 1, r, ql, qr);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

vector<array<int, 2>> events[MAX];
int n, k; 

ll check(int d){
    build(1, 1, n, d);
    ll a = 0, b = 0;
    for (int i = 1; i <= n; i++)
    {
        if((i - 1) % d == 0) lazy[1] ^= 1;
        for(auto& e:events[i]){
            update(1, 1, n, e[0], e[1]);
        }
        relax(1, 1, n);
        a += tree[1];
        b += n - tree[1];
    }
    return min(a, b);
}

void solve(){
    scanf("%d%d", &n, &k);
    for (int i = 0; i < k; i++)
    {
        int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        events[x1].push_back({y1, y2});
        events[x2 + 1].push_back({y1, y2});
    }
    ll ans = oo;
    for (int i = 1; i * i <= n; i++)
    {
        if(n % i == 0){
            ans = min(ans, check(i));
            if(i != 1){
                ans = min(ans, check(n / i));
            }
        }
    }
    cout << ans << '\n';
}

int main()
{
    solve();
}

컴파일 시 표준 에러 (stderr) 메시지

chessboard.cpp: In function 'void solve()':
chessboard.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
chessboard.cpp:73:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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