Submission #1186005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186005		juliany2	Intergalactic ship (IZhO19_xorsum)	C++20	0 / 100	10 ms	2368 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(d));
            memset(c, 0, sizeof(d));
            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 = (1 << u) * (1 << v) * i * (n - j + 1);

                    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;

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

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

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

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

In file included from /usr/include/string.h:535,
                 from /usr/include/c++/11/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:48,
                 from xorsum.cpp:1:
In function 'void* memset(void*, int, size_t)',
    inlined from 'int main()' at xorsum.cpp:36:19:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:59:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' writing 4056196 bytes into a region of size 4028 overflows the destination [-Wstringop-overflow=]
   59 |   return __builtin___memset_chk (__dest, __ch, __len,
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
   60 |                                  __glibc_objsize0 (__dest));
      |                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~
In function 'void* memset(void*, int, size_t)',
    inlined from 'int main()' at xorsum.cpp:37:19:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:59:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' writing 4056196 bytes into a region of size 4028 overflows the destination [-Wstringop-overflow=]
   59 |   return __builtin___memset_chk (__dest, __ch, __len,
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
   60 |                                  __glibc_objsize0 (__dest));
      |                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~

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