Submission #898165

#	Time	Username	Problem	Language	Result	Execution time	Memory
898165		Litusiano	Intergalactic ship (IZhO19_xorsum)	C++17	17 / 100	2045 ms	4296 KiB

xorsum

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include<bits/stdc++.h>
 // #include "perm.h"
using namespace std;
#define int long long 
const int MOD = 1e9+7;

signed main() {
	int n; cin>>n;
	vector<int> a(n); for(int& i : a) cin>>i;
	vector<tuple<int,int,int>> segs;
	int q; cin>>q;
	for(int i = 0; i<q; i++){
		int l,r,x; cin>>l>>r>>x; l--; r--; 
		segs.push_back({l,r,x});
	}
	int ans = 0;
	for(int i = 0; i < (1<<q); i++){
		vector<int> a1 = a;
		for(int j = 0; j<q; j++){
			if(i & (1<<j)){
				// CAN BE OPTIMIZED USING DIFFERENCE ARRAY
				int l,r,x; tie(l,r,x) = segs[j];
				for(int y = l; y<=r; y++) a1[y]^=x;
			}
			
		}
		vector<int> pre(n+1);
			for(int k= 0; k<n; k++) pre[k+1] = pre[k] + a1[k];
			for(int l = 0; l<n; l++){
				for(int r = l; r < n; r++){
					ans+= (pre[r+1] - pre[l]) * (pre[r+1] - pre[l]);
					ans%=MOD;
				}
			}
	}
	cout<<ans<<endl;
}

• 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