Submission #653507

#	Time	Username	Problem	Language	Result	Execution time	Memory
653507		becaido	Intergalactic ship (IZhO19_xorsum)	C++17	9 / 100	1081 ms	4260 KiB

xorsum

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

const int MOD = 1e9 + 7;
const int SIZE = 1005;
const int QSIZ = 1e5 + 5;

int n, q, ans;
int a[SIZE], pro[QSIZ];
int c1[SIZE], c2[SIZE], cnt[SIZE][SIZE];
tuple<int, int, int> ask[QSIZ];

inline pair<int, int> cal (int c) {
    if (c == 0) return {0, 1};
    return {pro[c - 1], pro[c - 1]};
}

void solve() {
    cin >> n;
    FOR (i, 1, n) cin >> a[i];
    pro[0] = 1;
    FOR (i, 1, max (q, 12)) pro[i] = (pro[i - 1] << 1) % MOD;
    cin >> q;
    FOR (i, 1, q) {
        auto &[l, r, x] = ask[i];
        cin >> l >> r >> x;
    }
    FOR (bi, 0, 6) FOR (bj, 0, 6) {
        fill (c1, c1 + n + 1, 0);
        fill (c2, c2 + n + 1, 0);
        FOR (i, 1, n) fill (cnt[i], cnt[i] + n + 1, 0);
        FOR (i, 1, q) {
            auto [l, r, x] = ask[i];
            if (x >> bi & 1) c1[l]++, c1[r + 1]--;
            if (x >> bj & 1) c2[l]++, c2[r + 1]--;
            if (x >> bi & 1 && x >> bj & 1) {
                cnt[l][l]++, cnt[l][r + 1]--;
                cnt[r + 1][l]--, cnt[r + 1][r + 1]++;
            }
        }
        FOR (i, 1, n) {
            c1[i] += c1[i - 1];
            c2[i] += c2[i - 1];
            FOR (j, 1, n) cnt[i][j] += cnt[i][j - 1];
            FOR (j, 1, n) cnt[i][j] += cnt[i - 1][j];
        }
        FOR (i, 1, n) FOR (j, 1, n) {
            auto [Odd, Even] = cal (cnt[i][j]);
            auto [odd1, even1] = cal (c1[i] - cnt[i][j]);
            auto [odd2, even2] = cal (c2[j] - cnt[i][j]);
            if (a[i] >> bi & 1) swap (odd1, even1);
            if (a[j] >> bj & 1) swap (odd2, even2);
            int val = (1ll * Odd * even1 % MOD * even2 + 1ll * Even * odd1 % MOD * odd2) % MOD;
            val = 1ll * val * pro[q - c1[i] - c2[j] + cnt[i][j]] % MOD;
            val = 1ll * val * min (i, j) % MOD * (n - max (i, j) + 1) % MOD;
            val = 1ll * pro[bi + bj] * val % MOD;
            ans = (ans + val) % MOD;
        }
    }
    cout << ans << '\n';
}

int main() {
    Waimai;
    solve();
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 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