oj.uz

Submission #378783

# Submission time Handle Problem Language Result Execution time Memory
378783 2021-03-17T04:09:04 Z abc864197532 Chessboard (IZhO18_chessboard) C++17
47 / 100
 2000 ms 224884 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;
};
 
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][2];
    for (int i = 0, x1, y1, x2, y2; i < m; ++i) {
        cin >> x1 >> y1 >> x2 >> y2, --x1, --y1;
        block[x1][1].pb({y1, y2});
        block[x2][0].pb({y1, y2});
    }
    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][0]) root.modify(j.l, j.r, false);
            for (range &j : block[i][1]) root.modify(j.l, j.r, true);
            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:28:53: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     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:40:37: warning: 'root.Seg::ch[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |         else sum = ch[0]->sum + ch[1]->sum;
      |                                 ~~~~^
chessboard.cpp:68:13: note: 'root.Seg::ch[1]' was declared here
   68 |         Seg root(0, n, k);
      |             ^~~~
chessboard.cpp:40:37: warning: 'root.Seg::ch[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |         else sum = ch[0]->sum + ch[1]->sum;
      |                                 ~~~~^
chessboard.cpp:68:13: note: 'root.Seg::ch[0]' was declared here
   68 |         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 492 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 11784 KB Output is correct
2 Correct 24 ms 2956 KB Output is correct
3 Correct 99 ms 14064 KB Output is correct
4 Correct 40 ms 1772 KB Output is correct
5 Correct 84 ms 11244 KB Output is correct
6 Correct 52 ms 9068 KB Output is correct
7 Correct 12 ms 4076 KB Output is correct
8 Correct 54 ms 9176 KB Output is correct
9 Correct 125 ms 8428 KB Output is correct
10 Correct 71 ms 8044 KB Output is correct

Subtask #3
15.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 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 388 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 3 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct

Subtask #4
16.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 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 388 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 3 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 36 ms 1540 KB Output is correct
17 Correct 57 ms 3304 KB Output is correct
18 Correct 134 ms 3436 KB Output is correct
19 Correct 624 ms 5536 KB Output is correct
20 Correct 681 ms 5352 KB Output is correct
21 Correct 50 ms 3180 KB Output is correct
22 Correct 4 ms 1772 KB Output is correct
23 Correct 90 ms 2360 KB Output is correct
24 Correct 107 ms 3308 KB Output is correct
25 Correct 19 ms 1388 KB Output is correct
26 Correct 65 ms 2284 KB Output is correct
27 Correct 188 ms 3180 KB Output is correct
28 Correct 107 ms 3180 KB Output is correct
29 Correct 47 ms 1516 KB Output is correct
30 Correct 5 ms 748 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 11784 KB Output is correct
2 Correct 24 ms 2956 KB Output is correct
3 Correct 99 ms 14064 KB Output is correct
4 Correct 40 ms 1772 KB Output is correct
5 Correct 84 ms 11244 KB Output is correct
6 Correct 52 ms 9068 KB Output is correct
7 Correct 12 ms 4076 KB Output is correct
8 Correct 54 ms 9176 KB Output is correct
9 Correct 125 ms 8428 KB Output is correct
10 Correct 71 ms 8044 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 2 ms 388 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 3 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 36 ms 1540 KB Output is correct
27 Correct 57 ms 3304 KB Output is correct
28 Correct 134 ms 3436 KB Output is correct
29 Correct 624 ms 5536 KB Output is correct
30 Correct 681 ms 5352 KB Output is correct
31 Correct 50 ms 3180 KB Output is correct
32 Correct 4 ms 1772 KB Output is correct
33 Correct 90 ms 2360 KB Output is correct
34 Correct 107 ms 3308 KB Output is correct
35 Correct 19 ms 1388 KB Output is correct
36 Correct 65 ms 2284 KB Output is correct
37 Correct 188 ms 3180 KB Output is correct
38 Correct 107 ms 3180 KB Output is correct
39 Correct 47 ms 1516 KB Output is correct
40 Correct 5 ms 748 KB Output is correct
41 Correct 1997 ms 224884 KB Output is correct
42 Correct 353 ms 37996 KB Output is correct
43 Correct 1031 ms 112576 KB Output is correct
44 Correct 449 ms 37900 KB Output is correct
45 Correct 205 ms 19304 KB Output is correct
46 Execution timed out 2066 ms 206652 KB Time limit exceeded
47 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 492 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 99 ms 11784 KB Output is correct
10 Correct 24 ms 2956 KB Output is correct
11 Correct 99 ms 14064 KB Output is correct
12 Correct 40 ms 1772 KB Output is correct
13 Correct 84 ms 11244 KB Output is correct
14 Correct 52 ms 9068 KB Output is correct
15 Correct 12 ms 4076 KB Output is correct
16 Correct 54 ms 9176 KB Output is correct
17 Correct 125 ms 8428 KB Output is correct
18 Correct 71 ms 8044 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 2 ms 492 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 2 ms 388 KB Output is correct
25 Correct 2 ms 364 KB Output is correct
26 Correct 3 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 2 ms 364 KB Output is correct
32 Correct 2 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Correct 36 ms 1540 KB Output is correct
35 Correct 57 ms 3304 KB Output is correct
36 Correct 134 ms 3436 KB Output is correct
37 Correct 624 ms 5536 KB Output is correct
38 Correct 681 ms 5352 KB Output is correct
39 Correct 50 ms 3180 KB Output is correct
40 Correct 4 ms 1772 KB Output is correct
41 Correct 90 ms 2360 KB Output is correct
42 Correct 107 ms 3308 KB Output is correct
43 Correct 19 ms 1388 KB Output is correct
44 Correct 65 ms 2284 KB Output is correct
45 Correct 188 ms 3180 KB Output is correct
46 Correct 107 ms 3180 KB Output is correct
47 Correct 47 ms 1516 KB Output is correct
48 Correct 5 ms 748 KB Output is correct
49 Correct 1997 ms 224884 KB Output is correct
50 Correct 353 ms 37996 KB Output is correct
51 Correct 1031 ms 112576 KB Output is correct
52 Correct 449 ms 37900 KB Output is correct
53 Correct 205 ms 19304 KB Output is correct
54 Execution timed out 2066 ms 206652 KB Time limit exceeded
55 Halted 0 ms 0 KB -