Submission #331940

#	Time	Username	Problem	Language	Result	Execution time	Memory
331940		keko37	Intergalactic ship (IZhO19_xorsum)	C++14	100 / 100	219 ms	5100 KiB

xorsum

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;

const int MAXN = 1005;
const int MAXQ = 200005;
const int MOD = 1000000007;

int n, q, ans;
llint sol[MAXQ];
int w[MAXN], lef[MAXQ], rig[MAXQ], val[MAXQ];
int cnt[MAXN][7], del[7][MAXN][7];
vector <int> v[MAXN], r[MAXN];

void precompute () {
    int br[7];
    memset(br, 0, sizeof br);
    for (int i = 0; i < n; i++) {
        for (auto q : v[i]) {
            for (int j = 0; j < 7; j++) {
                if (val[q] & (1 << j)) br[j]++;
            }
        }
        for (int j = 0; j < 7; j++) cnt[i][j] = br[j];
        for (auto q : r[i]) {
            for (int j = 0; j < 7; j++) {
                if (val[q] & (1 << j)) br[j]--;
            }
        }
    }
}

void upd (int q, int k) {
    for (int i = 0; i < 7; i++) {
        if (!(val[q] & (1 << i))) continue;
        for (int j = 0; j < 7; j++) {
            if (val[q] & (1 << j)) del[i][lef[q]][j] += k;
        }
    }
}

void sweep () {
    int br[7][7];
    for (int i = 0; i < n; i++) {
        for (auto q : v[i]) upd(q, +1);
        bool bta, btb;
        memset(br, 0, sizeof br);
        for (int a = 0; a < 7; a++) {
            bta = w[i] & (1 << a);
            for (int j = 0; j <= i; j++) {
                int d = (j + 1) * (n - i);
                if (j < i) d *= 2;
                for (int b = 0; b < 7; b++) {
                    br[a][b] += del[a][j][b];
                    btb = w[j] & (1 << b);

                    int samo_a = cnt[i][a] - br[a][b];
                    int samo_b = cnt[j][b] - br[a][b];
                    //cout << "bla " << i << " " << a << "    " << j << " " << b << "     " << samo_a << " " << samo_b << " " << br[a][b] << endl;
                    if (samo_a > 0 && samo_b > 0) {
                        sol[a + b + q - 2] += d;
                    } else if (samo_a == 0 && samo_b == 0) {
                        if (bta == btb) {
                            if (br[a][b] > 0) sol[a + b + q - 1] += d; else if (bta == 1) sol[a + b + q] += d;
                        }
                    } else if (samo_a == 0) {
                        if (br[a][b] > 0) sol[a + b + q - 2] += d; else if (bta == 1) sol[a + b + q - 1] += d;
                    } else {
                        if (br[a][b] > 0) sol[a + b + q - 2] += d; else if (btb == 1) sol[a + b + q - 1] += d;
                    }
                }
            }
        }
        for (auto q : r[i]) upd(q, -1);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> lef[i] >> rig[i] >> val[i];
        lef[i]--; rig[i]--;
        v[lef[i]].push_back(i);
        r[rig[i]].push_back(i);
    }
    precompute();
    sweep();
    int pot = 1;
    for (int i = 0; i < q + 20; i++) {
        sol[i] %= MOD;
        ans = (ans + (llint) pot * sol[i]) % MOD;
        pot = pot * 2 % MOD;
    }
    cout << ans;
    return 0;
}

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