제출 #1138756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138756		AHOKA	Intergalactic ship (IZhO19_xorsum)	C++20	9 / 100	2096 ms	3512 KiB

xorsum

#pragma GCC optimize("O3") 

#include <bits/stdc++.h>

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define int long long
#define double long double
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) / 2)
#define lc (2 * id)
#define rc (lc + 1)

const int maxn = 1e6 + 10, maxm = 5e3 + 10, oo = 1e18 + 10, lg = 8, sq = 350, mod = 1e9 + 7;

int n, m, a[maxn], b[maxn];

vector<ppp> q;

/*int seg[lg][maxn << 2], lazy[maxn << 2];

void merge(int id){
    for (int b = 0; b < lg;b++)
        seg[b][id] = seg[b][lc] + seg[b][rc];
}

void build(int id = 1, int l = 1, int r = n + 1){
    lazy[id] = 0;

    if (r - l == 1)
    {
        for (int b = 0; b < lg;b++)
            seg[b][id] = ((a[l] >> b) & 1ll);
            
        return;
    }

    build(lc, l, mid);
    build(rc, mid, r);

    merge(id);
}

void add(int id, int l, int r, int val){
    lazy[id] ^= val;

    for (int b = 0; b < lg; b++)
        if(val & (1ll << b))
            seg[b][id] = (r - l) - seg[b][id];
}

void relax(int id, int l, int r){
    if (!lazy[id])
        return;

    add(lc, l, mid, lazy[id]);
    add(rc, mid, r, lazy[id]);

    lazy[id] = 0;
}

void upd(int ql, int qr, int val, int id = 1, int l = 1, int r = n + 1){
    if(r <= ql || qr <= l)
        return;

    if(ql <= l && r <= qr){
        add(id, l, r, val);
        return;
    }

    relax(id, l, r);

    upd(ql, qr, val, lc, l, mid);
    upd(ql, qr, val, rc, mid, r);

    merge(id);
}*/

signed main()
{
	threesum;
    cin >> n;
    for (int i = 1; i <= n;i++){
        cin >> a[i];
        b[i] = a[i];
    }

    cin >> m;
    for (int i = 1; i <= m;i++){
        int l, r, x;
        cin >> l >> r >> x;
        q.push_back({x, {l, r}});
    }

    int ans = 0;

    for (int mask = 0; mask < (1ll << m); mask++){

        for (int i = 0; i < m; i++)
            if(mask & (1ll << i))
                for (int j = q[i].S.F; j <= q[i].S.S;j++)
                    b[j] ^= q[i].F;

        int res = 0;

        for (int i = 1; i <= n; i++){
            int s = 0;
            for (int j = i; j <= n; j++){
                (s += b[j]) %= mod;
                (res += (s * s) % mod) %= mod;
            }
        }

        for (int i = 0; i < m; i++)
            if(mask & (1ll << i))
                for (int j = q[i].S.F; j <= q[i].S.S;j++)
                    b[j] ^= q[i].F;

        (ans += res) %= mod;
    }

    cout << ans;
}

• 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