Submission #378776

#	Time	Username	Problem	Language	Result	Execution time	Memory
378776		abc864197532	Chessboard (IZhO18_chessboard)	C++17	8 / 100	101 ms	12140 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) {\
    for (auto a : x) cout << x << ' ';\
    cout << endl;\
}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N = 2000000;
 
struct range {
    int l, r;
    bool v;
};
 
struct Seg {
    int l, r, m, tag, sum;
    bool lz;
    Seg* ch[2];
    Seg (int _l, int _r, int k) : l(_l), r(_r), m(l + r >> 1), sum(0), lz(false) {
        if (r - l > 1) {
            ch[0] = new Seg(l, m, k);
            ch[1] = new Seg(m, r, k);
            tag = ch[0]->tag + ch[1]->tag;
        } else {
            tag = (l / k) & 1 ? -1 : 1;
        }
    }
    void pull() {
        if (lz) sum = tag;
        else if (r - l == 1) sum = 0;
        else sum = ch[0]->sum + ch[1]->sum;
    }
    void modify(int a, int b, bool v) {
        if (a <= l && r <= b) lz = v;
        else {
            if (a < m) ch[0]->modify(a, b, v);
            if (m < b) ch[1]->modify(a, b, v);
        }
        pull();
    }
};
 
int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <int> p;
    for (int i = 1; i < n; ++i) if (n % i == 0) p.pb(i);
    vector <range> block[n + 1];
    for (int i = 0, x1, y1, x2, y2; i < m; ++i) {
        cin >> x1 >> y1 >> x2 >> y2, --x1, --y1;
        block[x1].pb({y1, y2, true});
        block[x2].pb({y1, y2, false});
    }
    lli ans = 1ll * n * n;
    for (int k : p) {
        lli cur = 1ll * k * k * (1ll * (n / k) * (n / k) / 2);
        Seg root(0, n, k);
        for (int i = 0; i <= n; ++i) {
            for (range &j : block[i]) {
                root.modify(j.l, j.r, j.v);
            }
            if ((i / k) & 1) {
                cur -= root.sum;
            } else {
                cur += root.sum;
            }
        }
        ans = min({ans, cur, 1ll * n * n - cur});
    }
    cout << ans << endl;
}
 
/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
 */

Compilation message (stderr)

chessboard.cpp: In constructor 'Seg::Seg(int, int, int)':
chessboard.cpp:29:53: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     Seg (int _l, int _r, int k) : l(_l), r(_r), m(l + r >> 1), sum(0), lz(false) {
      |                                                   ~~^~~
chessboard.cpp: In function 'int main()':
chessboard.cpp:41:37: warning: 'root.Seg::ch[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |         else sum = ch[0]->sum + ch[1]->sum;
      |                                 ~~~~^
chessboard.cpp:69:13: note: 'root.Seg::ch[1]' was declared here
   69 |         Seg root(0, n, k);
      |             ^~~~
chessboard.cpp:41:37: warning: 'root.Seg::ch[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |         else sum = ch[0]->sum + ch[1]->sum;
      |                                 ~~~~^
chessboard.cpp:69:13: note: 'root.Seg::ch[0]' was declared here
   69 |         Seg root(0, n, k);
      |             ^~~~

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