Submission #286974

#	Time	Username	Problem	Language	Result	Execution time	Memory
286974		oolimry	Intergalactic ship (IZhO19_xorsum)	C++14	17 / 100	2079 ms	3308 KiB

xorsum

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef long long lint;
typedef pair<int,int> ii;

int arr[1005];
struct query{ int l, r, x; };

vector<query> queries;

bool in(int x, int bit){
	return ((x & (1 << bit)) != 0);
}

lint mod = 1000000007;
lint two[100005];
lint ans = 0;

lint odd(int N){
	if(N == 0) return 0;
	else return two[N-1];
}
lint even(int N){
	if(N == 0) return 1;
	else return two[N-1];
}
void fix(lint &x){
	x %= mod;
	if(x < 0) x += mod;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	lint n; cin >> n;
	for(int i = 1;i <= n;i++) cin >> arr[i];
	
	int Q; cin >> Q;
	for(int q = 0;q < Q;q++){
		queries.push_back({});
		query &QQ = queries.back();
		cin >> QQ.l >> QQ.r >> QQ.x;
	}
	
	two[0] = 1;
	for(int i = 1;i <= 100004;i++) two[i] = (two[i-1] * 2);

	for(lint a = 1;a <= n;a++){
		for(lint b = 1;b <= n;b++){
			for(int aBit = 0;aBit < 7;aBit++){
				for(int bBit = 0;bBit < 7;bBit++){
					lint none = 0;
					lint onlyA = 0;
					lint onlyB = 0;
					lint both = 0;
					for(query q : queries){
						bool A = false, B = false;
						int l = q.l, r = q.r, x = q.x;
						
						if(in(x, aBit) && l <= a && a <= r) A = true;
						if(in(x, bBit) && l <= b && b <= r) B = true;
						
						if(A && B) both++;
						else if(A) onlyA++;
						else if(B) onlyB++;
						else none++;
					}
					
					//cout << a << " " << b << " " << aBit << " " << bBit << ": " << none << " " << onlyA << " " << onlyB << " " << both << "\n";
					
					///don't use "both"
					lint res = two[none] * two[aBit + bBit];
					fix(res);
					res *= min(a,b) * (n - max(a,b) + 1);
					fix(res);
					
					
					if(in(arr[a], aBit)) res *= even(onlyA);
					else res *= odd(onlyA);
					fix(res);
					
					if(in(arr[b], bBit)) res *= even(onlyB);
					else res *= odd(onlyB);
					fix(res);
					
					res *= even(both);
					fix(res);
					
					
					ans += res;
					fix(ans);
					//cout << res << " ";
					
					
					///use "both"
					res = two[none] * two[aBit + bBit];
					fix(res);
					res *= min(a,b) * (n - max(a,b) + 1);
					fix(res);
					
					if(in(arr[a], aBit)) res *= odd(onlyA);
					else res *= even(onlyA);
					fix(res);
					
					if(in(arr[b], bBit)) res *= odd(onlyB);
					else res *= even(onlyB);
					fix(res);
					
					res *= odd(both);
					fix(res);
					
					ans += res;
					fix(ans);	
				}
			}
		} 
	}
	
	cout << ans << "\n";
}

• 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