Submission #1186564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186564		juliany2	Intergalactic ship (IZhO19_xorsum)	C++20	26 / 100	349 ms	6216 KiB

xorsum

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7;

const int N = 1007, M = 1e5 + 7;
ll p2[M];
int n, m;
int a[N];
array<int, 3> q[M];
int b[N], c[N], d[N][N];

int main() {
    cin.tie(0)->sync_with_stdio(false);

    p2[0] = 1;
    for (int i = 1; i < M; i++) {
        p2[i] = p2[i - 1] * 2 % mod;
    }

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    cin >> m;

    for (int i = 1; i <= m; i++)
        cin >> q[i][0] >> q[i][1] >> q[i][2];

    ll ans = 0;
    for (int u = 0; u < 7; u++) {
        for (int v = 0; v < 7; v++) {
            memset(b, 0, sizeof(b));
            memset(c, 0, sizeof(c));
            memset(d, 0, sizeof(d));

            for (int i = 1; i <= m; i++) {
                auto &[l, r, x] = q[i];

                if (x >> u & 1)
                    b[l]++, b[r + 1]--;
                if (x >> v & 1)
                    c[l]++, c[r + 1]--;
                if ((x >> u & 1) && (x >> v & 1))
                    d[l][r]++;
            }

            for (int j = 1; j <= n; j++) {
                for (int i = 1; i <= j; i++)
                    d[i][j] += d[i - 1][j];
            }

            for (int i = 1; i <= n; i++) {
                b[i] += b[i - 1];
                c[i] += c[i - 1];

                for (int j = n; j >= i; j--)
                    d[i][j] += d[i][j + 1];
            }

            for (int i = 1; i <= n; i++) {
                for (int j = i; j <= n; j++) {
                    array<ll, 2> l = {0, 0};
                    array<ll, 2> r = {0, 0};
                    int lo = b[i] - d[i][j], ro = c[j] - d[i][j];

                    if (lo == 0)
                        l[a[i] >> u & 1] = 1;
                    else
                        l[0] = l[1] = p2[lo - 1];

                    if (ro == 0)
                        r[a[j] >> v & 1] = 1;
                    else
                        r[0] = r[1] = p2[ro - 1];

                    ll here = 1LL * (1 << u) * (1 << v) * i * (n - j + 1) % mod;

                    if (d[i][j] == 0)
                        (here *= l[1] * r[1] % mod) %= mod;
                    else
                        (here *= ((l[0] * r[0] % mod) + (l[1] * r[1] % mod)) * p2[d[i][j] - 1] % mod) % mod;

                    (here *= p2[m - (lo + ro + d[i][j])]) %= mod;

                    if (i != j)
                        (here *= 2) %= mod;

                    (ans += here) %= mod;
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 0 / 11
• Subtask 7: 0 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8