Submission #1172129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172129		mactoddlover	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	938 ms	13844 KiB

xorsum

#include<bits/stdc++.h>

#define fi first
#define se second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)(v).size()

#define endl "\n"
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){
    if(a > b) return a = b, true;
    return false;
}

template<class T> bool maximize(T& a, T b){
    if(a < b) return a = b, true;
    return false;
}

typedef long long ll;

void fastIO(){
    ios_base::sync_with_stdio(NULL); cin.tie(0);
#ifdef LOCAL
    freopen("task.INP", "r", stdin);
    freopen("task.OUT", "w", stdout);
#endif
}

const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;

int add(int a, int b) {if(a >= MOD - b) return a - MOD + b; return a + b;}
int mul(int a, int b) {return 1LL*a*b % MOD;}

int n, q;
int a[1005];
int L[MAX], R[MAX], X[MAX];
int pw2[MAX];
int answer = 0;
int flip[3][1005][1005];

void add_contribution(int bit1, int bit2){
    for(int k = 0; k < 3; k++){
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= n; j++) flip[k][i][j] = 0;
        }
    }

    auto update_rect = [&](int type, int x1, int y1, int x2, int y2) -> void{
        flip[type][x1][y1]++;
        flip[type][x2+1][y1]--;
        flip[type][x1][y2+1]--;
        flip[type][x2+1][y2+1]++;
    };

    for(int i = 1; i <= q; i++){
        int on_bit1 = (X[i] >> bit1) & 1;
        int on_bit2 = (X[i] >> bit2) & 1;
        if(on_bit1 && on_bit2){
            update_rect(0, L[i], L[i], R[i], R[i]);
            update_rect(2, 1, L[i], L[i] - 1, R[i]);
            update_rect(1, L[i], R[i] + 1, R[i], n);
        }
        else if(on_bit1){
            update_rect(1, L[i], 1, R[i], n);
        }
        else if(on_bit2){
            update_rect(2, 1, L[i], n, R[i]);
        }
    }

    auto contrib = [&](int n, int bit) -> int{
        if(!n) return bit ^= 1;
        return pw2[n-1];
    };

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 0; k < 3; k++){
                flip[k][i][j] += flip[k][i-1][j] + flip[k][i][j-1]  - flip[k][i-1][j-1];
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            int on_bit1 = (a[i] >> bit1) & 1;
            int on_bit2 = (a[j] >> bit2) & 1;

            int ways = 0;

            for(int st0 = 0; st0 < 2; st0++){
                for(int st1 = 0; st1 < 2; st1++){
                    for(int st2 = 0; st2 < 2; st2++){

                        int state_bit1 = (on_bit1 + st0 + st1) & 1;
                        int state_bit2 = (on_bit2 + st0 + st2) & 1;

                        if(state_bit1 && state_bit2){
                            int tmp = contrib(flip[0][i][j], st0);
                            tmp = mul(tmp, contrib(flip[1][i][j], st1));
                            tmp = mul(tmp, contrib(flip[2][i][j], st2));
                            ways = add(ways, tmp);
                        }

                    }
                }
            }

            int unchanged = q;

            for(int k = 0; k < 3; k++) unchanged -= flip[k][i][j];

            assert(unchanged >= 0);

            ways = mul(ways, pw2[unchanged]);

            ways = mul(ways, (1 << bit1));
            ways = mul(ways, (1 << bit2));

            int same = 1 + (i != j);
            int cover = mul(i, n - j + 1);

            ways = mul(ways, mul(same, cover));

            answer = add(answer, ways);
        }
    }
}

signed main(){
    fastIO();

    cin >> n;

    for(int i = 1; i <= n; i++) cin >> a[i];

    cin >> q;

    for(int i = 1; i <= q; i++) cin >> L[i] >> R[i] >> X[i];

    pw2[0] = 1;

    for(int i = 1; i <= q; i++) pw2[i] = mul(pw2[i-1], 2);

    const int lg = 7;

    for(int i = 0; i < lg; i++){
        for(int j = 0; j < lg; j++){
            add_contribution(i, j);
        }
    }

    cout << answer;
}

• 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