Submission #1132753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132753		Muhammet	Intergalactic ship (IZhO19_xorsum)	C++20	100 / 100	1098 ms	14628 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 += 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 x = 0; x <= 7; x++){
		for(int y = 0; y <= 7; y++){
			// cout << x << ' ' << y << "\n";
			vector <vector <int>> dp(n+2, vector <int> (n+2,0));
			vector <int> dp1(n+2, 0), dp2(n+2, 0);
			for(int i = 1; i <= q; i++){
				bool t1 = ((b[i]>>x)&1), t2 = ((b[i]>>y)&1);
				// cout << t1 << ' ' << t2 << '\n';
				if(t1 == 1 and t2 == 1){
					dp[l[i]][l[i]]++, dp[l[i]][r[i]+1]--, dp[r[i]+1][l[i]]--, dp[r[i]+1][r[i]+1]++;
				}
				if(t1 == 1){
					dp1[l[i]]++, dp1[r[i]+1]--;
				}
				if(t2 == 1){
					dp2[l[i]]++, dp2[r[i]+1]--;
				}
			}
			for(int i = 1; i <= n; i++){
				dp1[i] += dp1[i-1];
				dp2[i] += dp2[i-1];
				for(int j = 1; j <= n; j++){
					dp[i][j] += (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]);
					// cout << dp[i][j] << ' ';
				}
				// cout << '\n';
			}
			// cout << '\n';
			for(int i = 1; i <= n; i++){
				for(int j = i; j <= n; j++){
					int A = dp[i][j], B = dp1[i] - A, C = dp2[j] - A;
					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)) % M;
					ans %= M;
				}
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

• 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