oj.uz

Submission #579404

# Submission time Handle Problem Language Result Execution time Memory
579404 2022-06-19T05:21:49 Z KoD Intergalactic ship (IZhO19_xorsum) C++17
100 / 100
 501 ms 193824 KB 
#include <bits/stdc++.h>

using std::array;
using std::pair;
using std::tuple;
using std::vector;

using ll = long long;

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

constexpr int MOD = 1000000007;

struct Fp {
    int x;
    Fp(const int x = 0) : x(x) {}

    Fp operator+(const Fp& t) { return Fp(*this) += t; }
    Fp& operator+=(const Fp& t) {
        x += t.x;
        if (x >= MOD)
            x -= MOD;
        return *this;
    }

    Fp operator-(const Fp& t) { return Fp(*this) -= t; }
    Fp& operator-=(const Fp& t) {
        x -= t.x;
        if (x < 0)
            x += MOD;
        return *this;
    }

    Fp operator*(const Fp& t) { return Fp(*this) *= t; }
    Fp& operator*=(const Fp& t) {
        x = (long long)x * t.x % MOD;
        return *this;
    }

    Fp pow(int e) const {
        Fp ret(1), mul(*this);
        while (e > 0) {
            if (e & 1)
                ret *= mul;
            mul *= mul;
            e >>= 1;
        }
        return ret;
    }
};

constexpr int MAX = 1001;
int A[MAX];
int C1[7][MAX];
int C2[7][7][MAX][MAX];

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }
    int Q;
    std::cin >> Q;
    for (int q = 0; q < Q; ++q) {
        int l, r, x;
        std::cin >> l >> r >> x;
        l -= 1;
        for (int d = 0; d < 7; ++d) {
            if (x >> d & 1) {
                C1[d][l] += 1;
                C1[d][r] -= 1;
                for (int e = 0; e < 7; ++e) {
                    if (x >> e & 1) {
                        C2[d][e][l][l] += 1;
                        C2[d][e][l][r] -= 1;
                        C2[d][e][r][l] -= 1;
                        C2[d][e][r][r] += 1;
                    }
                }
            }
        }
    }
    for (int d = 0; d < 7; ++d) {
        for (int i = 1; i <= N; ++i) {
            C1[d][i] += C1[d][i - 1];
        }
    }
    for (int d = 0; d < 7; ++d) {
        for (int e = 0; e < 7; ++e) {
            for (int i = 0; i <= N; ++i) {
                for (int j = 0; j <= N; ++j) {
                    if (i > 0)
                        C2[d][e][i][j] += C2[d][e][i - 1][j];
                    if (j > 0)
                        C2[d][e][i][j] += C2[d][e][i][j - 1];
                    if (i > 0 and j > 0)
                        C2[d][e][i][j] -= C2[d][e][i - 1][j - 1];
                }
            }
        }
    }
    Fp ans = 0;
    array<Fp, 4> inv = {};
    inv[0] = 1;
    for (int k = 0; k < 3; ++k) {
        inv[k + 1] = inv[k] * ((MOD + 1) / 2);
    }
    for (int d = 0; d < 7; ++d) {
        for (int e = 0; e < 7; ++e) {
            for (int i = 0; i < N; ++i) {
                for (int j = i; j < N; ++j) {
                    Fp coeff = Fp(1 << (d + e)) * (i == j ? 1 : 2) * (i + 1) * (N - j);
                    int c1 = C1[d][i], c2 = C1[e][j], c3 = C2[d][e][i][j];
                    c1 -= c3, c2 -= c3;
                    const int b0 = (A[i] >> d) & 1, b1 = (A[j] >> e) & 1;
                    const int t = (c1 > 0) + (c2 > 0) + (c3 > 0);
                    if (t >= 2) {
                        coeff *= inv[2];
                    } else if (c1 > 0) {
                        if (b1 == 0)
                            coeff = 0;
                        else
                            coeff *= inv[1];
                    } else if (c2 > 0) {
                        if (b0 == 0)
                            coeff = 0;
                        else
                            coeff *= inv[1];
                    } else if (c3 > 0) {
                        coeff *= b0 == b1 ? inv[1] : 0;
                    } else {
                        coeff *= b0 and b1;
                    }
                    ans += coeff;
                }
            }
        }
    }
    ans *= Fp(2).pow(Q);
    std::cout << ans.x << '\n';
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 11 ms 19924 KB Output is correct
7 Correct 12 ms 19924 KB Output is correct
8 Correct 14 ms 19924 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 20668 KB Output is correct
2 Correct 19 ms 20032 KB Output is correct
3 Correct 13 ms 19964 KB Output is correct
4 Correct 12 ms 19912 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 192548 KB Output is correct
2 Correct 432 ms 192508 KB Output is correct
3 Correct 380 ms 192620 KB Output is correct
4 Correct 372 ms 192508 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 6 ms 6460 KB Output is correct
5 Correct 4 ms 6484 KB Output is correct
6 Correct 4 ms 6488 KB Output is correct
7 Correct 4 ms 6484 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 11 ms 19924 KB Output is correct
7 Correct 12 ms 19924 KB Output is correct
8 Correct 14 ms 19924 KB Output is correct
9 Correct 3 ms 6484 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 4 ms 6484 KB Output is correct
12 Correct 12 ms 19864 KB Output is correct
13 Correct 12 ms 19924 KB Output is correct
14 Correct 13 ms 19948 KB Output is correct
15 Correct 13 ms 19944 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 11 ms 19924 KB Output is correct
7 Correct 12 ms 19924 KB Output is correct
8 Correct 14 ms 19924 KB Output is correct
9 Correct 3 ms 6484 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 4 ms 6484 KB Output is correct
12 Correct 6 ms 6460 KB Output is correct
13 Correct 4 ms 6484 KB Output is correct
14 Correct 4 ms 6488 KB Output is correct
15 Correct 4 ms 6484 KB Output is correct
16 Correct 12 ms 19864 KB Output is correct
17 Correct 12 ms 19924 KB Output is correct
18 Correct 13 ms 19948 KB Output is correct
19 Correct 13 ms 19944 KB Output is correct
20 Correct 200 ms 97848 KB Output is correct
21 Correct 159 ms 97884 KB Output is correct
22 Correct 179 ms 97740 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 11 ms 19924 KB Output is correct
7 Correct 12 ms 19924 KB Output is correct
8 Correct 14 ms 19924 KB Output is correct
9 Correct 51 ms 20668 KB Output is correct
10 Correct 19 ms 20032 KB Output is correct
11 Correct 13 ms 19964 KB Output is correct
12 Correct 12 ms 19912 KB Output is correct
13 Correct 378 ms 192548 KB Output is correct
14 Correct 432 ms 192508 KB Output is correct
15 Correct 380 ms 192620 KB Output is correct
16 Correct 372 ms 192508 KB Output is correct
17 Correct 3 ms 6484 KB Output is correct
18 Correct 3 ms 6484 KB Output is correct
19 Correct 4 ms 6484 KB Output is correct
20 Correct 6 ms 6460 KB Output is correct
21 Correct 4 ms 6484 KB Output is correct
22 Correct 4 ms 6488 KB Output is correct
23 Correct 4 ms 6484 KB Output is correct
24 Correct 12 ms 19864 KB Output is correct
25 Correct 12 ms 19924 KB Output is correct
26 Correct 13 ms 19948 KB Output is correct
27 Correct 13 ms 19944 KB Output is correct
28 Correct 200 ms 97848 KB Output is correct
29 Correct 159 ms 97884 KB Output is correct
30 Correct 179 ms 97740 KB Output is correct
31 Correct 449 ms 193548 KB Output is correct
32 Correct 460 ms 193824 KB Output is correct
33 Correct 414 ms 193376 KB Output is correct
34 Correct 501 ms 193312 KB Output is correct
35 Correct 428 ms 193380 KB Output is correct
36 Correct 413 ms 193356 KB Output is correct