Submission #1007428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007428		makrav	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	266 ms	16216 KiB

xorsum

#include <bits/stdc++.h>
  
using namespace std;
using ll = long long;
  
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first 
#define sc second

const int mod = 1e9 + 7;

int cnt[7][1000];
int add[1001][1001], pref[1001][1001];
ll sum_pw[200010];

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int q; cin >> q;
    vector<vector<int>> qrs(q, vector<int>(3));
    for (int i = 0; i < q; i++) {
        cin >> qrs[i][0] >> qrs[i][1] >> qrs[i][2];
        qrs[i][0]--;
        qrs[i][1]--;
    }
    for (int bit = 0; bit < 7; bit++) {
        vector<int> delta(n + 1, 0);
        for (int i = 0; i < q; i++) {
            if ((qrs[i][2] >> bit) & 1) {
                delta[qrs[i][0]]++;
                delta[qrs[i][1] + 1]--;
            }
        }
        int bal = 0;
        for (int i = 0; i < n; i++) {
            bal += delta[i];
            cnt[bit][i] = bal;
        }
    }
    for (int bit = 0; bit < 7; bit++) {
        for (int bit2 = 0; bit2 < 7; bit2++) {
            for (int i = 0; i < q; i++) {
                if (((qrs[i][2] >> bit) & 1) && ((qrs[i][2] >> bit2) & 1)) {
                    add[qrs[i][0]][qrs[i][0]]++;
                    add[qrs[i][0]][qrs[i][1] + 1]--;
                    add[qrs[i][1] + 1][qrs[i][0]]--;
                    add[qrs[i][1] + 1][qrs[i][1] + 1]++;
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    pref[i][j] = (i > 0 ? pref[i - 1][j] : 0) + (j > 0 ? pref[i][j - 1] : 0) - ((i > 0 && j > 0) ? pref[i - 1][j - 1] : 0) + add[i][j];
                    if (j >= i) {
                        int AD = q - (cnt[bit][i] + cnt[bit2][j] - pref[i][j]) + bit + bit2;
                        int C = (i + 1) * (n - j);
                        if (i != j)C*=2;

                        if (pref[i][j] == 0) {
                            if (cnt[bit][i] == 0 && ((a[i]>>bit)&1)==0)continue;
                            if (cnt[bit2][j]==0&&((a[j]>>bit2)&1)==0)continue;
                            int SS = max(0, cnt[bit][i] - 1) + max(0, cnt[bit2][j] - 1);
                            sum_pw[AD + SS] += C;
                        } else {
                            if (pref[i][j] == cnt[bit][i]) {
                                if (pref[i][j] == cnt[bit2][j]) {
                                    if (((a[i]>>bit)&1)==((a[j]>>bit2)&1)) {
                                        sum_pw[pref[i][j] - 1 + AD] += C;
                                    }
                                } else {
                                    sum_pw[cnt[bit2][j] - 2 + AD] += C;
                                }
                            } else {
                                if (pref[i][j] == cnt[bit2][j]) {
                                    sum_pw[cnt[bit][i] - 2 + AD] += C;
                                } else {
                                    sum_pw[AD + cnt[bit][i] + cnt[bit2][j] - pref[i][j] - 2] += C;
                                }
                            }
                        }
                    }
                }
            }
            for (int i = 0; i < q; i++) {
                if (((qrs[i][2] >> bit) & 1) && ((qrs[i][2] >> bit2) & 1)) {
                    add[qrs[i][0]][qrs[i][0]]--;
                    add[qrs[i][0]][qrs[i][1] + 1]++;
                    add[qrs[i][1] + 1][qrs[i][0]]++;
                    add[qrs[i][1] + 1][qrs[i][1] + 1]--;
                }
            }
        }
    }
    ll ans = 0, pw = 1;
    for (int i = 0; i < q + 20; i++) {
        ans += ((sum_pw[i] % mod) * 1ll * pw) % mod;
        ans %= mod;
        pw *= 2;
        pw %= mod;
    }
    cout << ans << '\n';

    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