Submission #1132645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132645		Muhammet	Intergalactic ship (IZhO19_xorsum)	C++20	17 / 100	2095 ms	6468 KiB

xorsum

#include <bits/stdc++.h>	
using namespace std;

#define ff first
#define ss second
#define int long long

const int N = 5e5 + 5;
const int M = 1e9 + 7;

int n, q, ans, c[N];

vector <int> a, l, r, b;

int f(bool x, bool y, int A, int B, int C){
	int k = 1;
	if(A > 0) {
		k = 1LL * f(x,y,0,B,C) * c[A-1] % M;
		// k = max(k, 1LL);
		k += 1LL * f((1-x),(1-y),0,B,C) * (c[A-1]) % M;
		return k % M;
	}
	if(A == 0){
		if(x == 0){
			if (B > 0) k = (1LL * k * c[B-1]) % M;
			else k = 0; 
		}
		else {
			if (B > 0) k = (1LL * k * c[B-1]) % M;
		}
		if(y == 0){
			if (C > 0) k = (1LL * k * c[C-1]) % M;
			else k = 0;
		}
		else {
			if(C > 0) k = (1LL * k * c[C-1]) % M;
		}
	}
	return k % M;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	
	cin >> n;
	a.resize(n+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	cin >> q;
	l.resize(q+1), r.resize(q+1), b.resize(q+1);
	for(int i = 1; i <= q; i++){
		cin >> l[i] >> r[i] >> b[i];
	}
	c[0] = 1;
	for(int i = 1; i < N; i++){
		c[i] = (c[i-1] * 2) % M;
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = i; j <= n; j++){
			for(int x = 0; x <= 7; x++){
				for(int y = 0; y <= 7; y++){
					int A = 0, B = 0, C = 0;
					for(int i1 = 1; i1 <= q; i1++){
						bool tr1 = (l[i1] <= i and r[i1] >= i), tr2 = (l[i1] <= j and r[i1] >= j);
						bool t1 = (b[i1]>>x)&1, t2 = (b[i1]>>y)&1;
						A += (tr1 + tr2 == 2 and t1 + t2 == 2);
						B += (tr1 == 1 and t1 == 1 and (t2 == 0 or tr2 == 0));
						C += (tr2 == 1 and t2 == 1 and (t1 == 0 or tr1 == 0));
					}
					int a1 = (1LL*i*(n-j+1)) % M, f1 = (f(((a[i]>>x)&1), ((a[j]>>y)&1), A, B, C) * 1LL * (i == j ? 1 : 2)) % M;
					ans += (1LL * a1 * c[x+y] % M) * (1LL * f1 * c[q - A - B - C]) % M;
					// cout << ans << '\n
					ans %= M;
				}
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

• 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