Submission #1132639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132639		Muhammet	Intergalactic ship (IZhO19_xorsum)	C++20	17 / 100	2094 ms	2372 KiB

xorsum

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

#define ff first
#define ss second
#define ll long long

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

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

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

ll f(bool x, bool y, ll A, ll B, ll C){
	ll k = 1;
	if(A > 0) {
		ll k1 = 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+k1;
	}
	if(A == 0){
		if(x == 0){
			if (B > 0) k = k * c[B-1] % M;
			else k = 0; 
		}
		else {
			if (B > 0) k = k * c[B-1] % M;
		}
		if(y == 0){
			if (C > 0) k = k * c[C-1] % M;
			else k = 0;
		}
		else {
			if(C > 0) k = k * c[C-1] % M;
		}
	}
	return k % M;
}

int 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 <= q; i++){
		c[i] = (c[i-1] * 2) % M;
	}
	ll 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++){
					ll 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 = ((1<<x)&b[i1]), t2 = ((1<<y)&b[i1]);
						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));
					}
					// cout << i << ' ' << j << ' ' << x << ' ' << y << ' ' << A << ' ' << B << ' ' << C << '\n';
					ll 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;
					// if((a[i]>>x)&1 == 1 and (a[j]>>y)&1 == 1 and f1 == 0) f1 = 1;
					ans +=  (a1 * ((1<<(x+y))) % M) * 1LL * f1 * (1 << (q - A - B - C)) % M;
					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