oj.uz

Submission #523548

# Submission time Handle Problem Language Result Execution time Memory
523548 2022-02-07T18:24:04 Z RaresFelix Chessboard (IZhO18_chessboard) C++17
0 / 100
 123 ms 7044 KB 
#include <bits/stdc++.h>

#define MN 107171
using ll = long long;
using namespace std;
int n, k;
tuple<int, int, int, int> R[MN];

namespace AINT {
    int V[4 * MN], LZ[4 * MN];
    void clear(int u = 1, int s = 1, int d = n) {
        V[u] = LZ[u] = 0;
        if(s != d)
            clear(u * 2, s, (s + d) /2), clear(u * 2 + 1, (s + d) / 2 + 1, d);
    }
    void prp(int u, int s, int d) {
        if(!LZ[u]) return;
        V[u] = d - s + 1 - V[u];
        LZ[u] = 0;
        if(s != d)
            LZ[u * 2] ^= 1, LZ[u * 2 + 1] ^= 1;
    }
    void update(int l, int r, int u = 1, int s = 1, int d = n) {
        prp(u, s, d);
        if(r < s || d < l) return;
        if(l <= s && d <= r) {
            LZ[u] ^= 1;
            prp(u, s, d);
            return;
        }
        update(l, r, u * 2, s, (s + d) / 2);
        update(l, r, u * 2 + 1, (s + d) / 2 + 1, d);
        V[u] = V[u * 2] + V[u * 2 + 1];
    }
}
vector<pair<int, int>> OP[MN];
ll acopera(int l, int c0) {
    if(l == n) return LLONG_MAX;
    ///c0 = 1 daca coloram primul patrat
    AINT::clear();
    for(int i = 1 + (1 - c0) * l; i <= n; i += 2 * l)
        AINT::update(i, i + l - 1);
    ll re = 0;
    for(int i = 1; i <= n; ++i) {
        if(i % l == 1 && i != 1)
            AINT::update(1, n);
        for(auto [l, r] : OP[i])
            AINT::update(l, r);
        re += AINT::V[1];
    }
    return re;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n >> k;
    ll re = LLONG_MAX;
    for (int i = 1, a, b, c, d; i <= k; ++i) {
        cin >> a >> b >> c >> d;
        R[i] = make_tuple(a, b, c, d);
        OP[a].emplace_back(b, d);
        OP[c + 1].emplace_back(b, d);
    }
    vector<int> D;
    for (int i = 1; i * i <= n; ++i)
        if (i * i == n) D.push_back(i);
        else if (n % i == 0)
            D.push_back(i), D.push_back(n / i);
    for (auto it: D)
        re = min(re, min(acopera(it, 0), acopera(it, 1)));
    cout << re << "\n";
    return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct
4 Correct 6 ms 2900 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 2828 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 4 ms 2764 KB Output is correct
10 Incorrect 3 ms 2764 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct
4 Correct 6 ms 2900 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 2828 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 4 ms 2764 KB Output is correct
10 Incorrect 3 ms 2764 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 30.0

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