Submission #602364

#	Time	Username	Problem	Language	Result	Execution time	Memory
602364		Ozy	Intergalactic ship (IZhO19_xorsum)	C++17	17 / 100	2055 ms	3440 KiB

xorsum

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 1000
#define MQ 100000
#define mod 1000000007

lli n,pot,act,a,q,res;
lli arr[MAX+2], l[MQ+2], r[MQ+2], k[MQ+2];
lli acu1[MAX+2],acu2[MAX+2],acu3[MAX+2],dp[MAX+2];
lli cambio[MAX+2],nuevo[MAX+2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    rep(i,1,n) cin >> arr[i];

    cin >> q;
    rep(i,1,q) cin >> l[i] >> r[i] >> k[i];

    res = 0;
    pot = 1<<q;
    act = 0;
    while (act < pot) {

        rep(i,1,n) cambio[i] = 0;
        rep(i,1,q) {
            a = 1<<(i-1);
            if (a&act) {
                cambio[ l[i] ] ^= k[i];
                cambio[ r[i]+1 ] ^= k[i];
            }
        }

        a = 0;
        rep(i,1,n) {
            a ^= cambio[i];
            nuevo[i] =  arr[i]^a;

            acu1[i] = acu1[i-1] + i*nuevo[i];
            acu2[i] = acu2[i-1] + i*nuevo[i]*nuevo[i];
            acu3[i] = acu3[i-1] + 2*nuevo[i]*acu1[i-1];

            dp[i] = dp[i-1] + acu2[i] + acu3[i];
        }

        res += dp[n];
        res %= mod;
        act++;
    }

    cout << res;
}

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