Submission #376261

#	Time	Username	Problem	Language	Result	Execution time	Memory
376261		ijxjdjd	Intergalactic ship (IZhO19_xorsum)	C++14	0 / 100	1386 ms	5944 KiB

xorsum

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXK = 7;
const int MAXN = 1000 + 5;
const int MAXQ = (int)(1e5) + 5;
int flip[MAXN][MAXK];
int dblflip[MAXN][MAXK][MAXK];
int cur[MAXK][MAXK];
int mv[MAXK][MAXK];
bool arr[MAXN][MAXK];

vector<pair<int, int>> add[MAXN];
vector<pair<int, int>> rem[MAXN];

ll pows[MAXQ];
ll MOD = (int)(1e9) + 7;
ll even(ll i) {
    if (i == 0) {
        return 1;
    }
    else {
        return pows[i-1];
    }
}
ll odd(ll i) {
    if (i == 0) {
        return 0;
    }
    else {
        return pows[i-1];
    }
}
ll mul(ll a, ll b) {
    return (a*b)%MOD;
}
int main() {
    pows[0] = 1;
    for (int i = 1; i < MAXQ; i++) {
        pows[i] = 2*pows[i-1];
        pows[i] %= MOD;
    }
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        for (int j = 0; j < MAXK; j++) {
            arr[i][j] = ((1<<j)&(a));
        }
	}
	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        l--, r--;
        add[l].push_back({r, x});
        for (int j = 0; j < MAXK; j++) {
            if ((1<<j)&x) {
                flip[l][j]++;
                flip[r+1][j]--;
            }
        }
	}
	for (int i = 0; i < MAXK; i++) {
        for (int j = 1; j < N; j++) {
            flip[j][i] += flip[j-1][i];
        }
	}
	ll res = 0;
	for (int i = 0; i < N; i++) {
        for (auto& p : add[i]) {
            for (int j = 0; j < MAXK; j++) {
                for (int k = 0; k < MAXK; k++) {
                    if (((1<<j)&p.second) && ((1<<k)&p.second)) {
                        cur[j][k]++;
                        dblflip[p.first+1][j][k]--;
                        rem[p.first+1].push_back({i, p.second});
                    }
                }
            }
        }
        for (auto& p : rem[i]) {
            for (int j = 0; j < MAXK; j++) {
                for (int k = 0; k < MAXK; k++) {
                    if (((1<<j)&p.second) && ((1<<k)&p.second)) {
                        cur[j][k]--;
                    }
                }
            }
        }
        for (int j = 0; j < MAXK; j++) {
            for (int k = 0; k < MAXK; k++) {
                mv[j][k] = cur[j][k];
            }
        }
        for (int j = i; j < N; j++) {
            if (j != i) {
                for (int b1 = 0; b1 < MAXK; b1++) {
                    for (int b2 = 0; b2 < MAXK; b2++) {
                        mv[b1][b2] += dblflip[j][b1][b2];
                    }
                }
            }
            for (int b1 = 0; b1 < MAXK; b1++) {
                for (int b2 = 0; b2 < MAXK; b2++) {
                    int X = flip[i][b1];
                    int Z = flip[j][b2];
                    int Y = mv[b1][b2];
                    X -= Y;
                    Z -= Y;
                    if (arr[i][b1] && arr[j][b2]) {
                        res += mul(i+1, N-j) * (i != j ? 2 : 1)*mul(pows[Q-X-Y-Z], mul(pows[b1+b2], (mul(even(X), mul(even(Y), even(Z)))) + mul(odd(Y), mul(odd(X), odd(Z)))));
                    }
                    else if (!arr[i][b1] && arr[j][b2]) {
                        res += mul(i+1, N-j) *(i != j ? 2 : 1)*mul(pows[Q-X-Y-Z], mul(pows[b1+b2], (mul(odd(X), mul(even(Y), even(Z)))) + mul(odd(Y), mul(even(X), odd(Z)))));
                    }
                    else if (arr[i][b1] && !arr[j][b2]) {
                        res += mul(i+1, N-j)*(i != j ? 2 : 1) * mul(pows[Q-X-Y-Z], mul(pows[b1+b2], (mul(even(X), mul(even(Y), odd(Z)))) + mul(odd(Y), mul(odd(X), even(Z)))));
                    }
                    else {
                        res += mul(i+1, N-j) * (i != j ? 2 : 1) * mul(pows[Q-X-Y-Z], mul(pows[b1+b2], (mul(odd(X), mul(even(Y), odd(Z)))) + mul(odd(Y), mul(even(X), even(Z)))));
                    }
                    res %= MOD;
                }
            }
        }
	}
	cout << res << '\n';
	return 0;
}

• 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