oj.uz

Submission #378776

# Submission time Handle Problem Language Result Execution time Memory
378776 2021-03-17T04:05:20 Z abc864197532 Chessboard (IZhO18_chessboard) C++17
8 / 100
 101 ms 12140 KB 
#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

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.0 / 8.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 10220 KB Output is correct
2 Correct 17 ms 2796 KB Output is correct
3 Correct 64 ms 12140 KB Output is correct
4 Incorrect 35 ms 2668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 10220 KB Output is correct
2 Correct 17 ms 2796 KB Output is correct
3 Correct 64 ms 12140 KB Output is correct
4 Incorrect 35 ms 2668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 101 ms 10220 KB Output is correct
10 Correct 17 ms 2796 KB Output is correct
11 Correct 64 ms 12140 KB Output is correct
12 Incorrect 35 ms 2668 KB Output isn't correct
13 Halted 0 ms 0 KB -