Submission #469696

#	Time	Username	Problem	Language	Result	Execution time	Memory
469696		keta_tsimakuridze	Intergalactic ship (IZhO19_xorsum)	C++14	100 / 100	1787 ms	7752 KiB

xorsum

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
#define ll long long
using namespace std;
const int N = 1e3 + 5, M = 1e5 + 5, mod = 1e9 + 7; // !
int a[N],n,Q,ch[M][2],pwr[M],dp[N][N],p[5][N];
vector<pair<pii,int> > all;
int choose(int x,int t) {
	return ch[x][t];
}
main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	cin >> Q;
	for(int j = 1; j <= Q; j++) {
		int l,r,x;
		cin >> l >> r >> x;
		all.push_back({{l,r},x});
	}
	
	ch[0][0] = 1;
	pwr[0] = 1;
	for(int i = 1; i <= Q; i++) {
		for(int t = 0; t < 2; t++){
			ch[i][t] = ch[i - 1][t] + ch[i - 1][1 - t];
			ch[i][t] %= mod;
		}
		pwr[i] = pwr[i - 1] * 2 % mod;
	}
	int ans = 0;
	for(int t1 = 0; t1 < 8; t1++) {
		for(int t2 = 0; t2 < 8; t2++) {
			for(int t = 0; t < 3; t++) 
			for(int i = 1; i <= n; i++) {
				p[t][i] = 0;
				for(int j = 1; j <= n; j++) dp[i][j] = 0;
			}
			for(int i = 0; i < Q; i++){
				int l = all[i].f.f, r = all[i].f.s, x = all[i].s;
				if((x & (1 << t1)) && (x & (1 << t2))) {
					dp[l][r]++;
					p[2][l]++;
					p[2][r + 1]--;
				}
				else if(x & (1 << t1)) p[0][l]++, p[0][r + 1]--;
				else if(x & (1 << t2)) p[1][l]++, p[1][r + 1]--;
			}
			
			for(int l = 1; l <= n; l++) {
				for(int r = n; r >= l; r--) dp[l][r] += dp[l - 1][r] + dp[l][r + 1] - dp[l - 1][r + 1];
			}
			for(int t = 0; t < 3; t++)
			for(int i = 1; i <= n; i++) {
				p[t][i] += p[t][i - 1];
			}
			for(int l = 1; l <= n; l++) {
				for(int r = l; r <= n; r++) {
					int b1 =( (1 << t1) & a[l] ) > 0;
					int b2 = ( (1 << t2) & a[r] ) > 0;
					int P = (ll)(1 << t1) % mod * (1 << t2) % mod 
							* l % mod * (n - r + 1) % mod* pwr[Q - p[0][l] - p[1][r] - p[2][l] - p[2][r] + dp[l][r] ] % mod;
					if(l < r) P *= 2;
					P %= mod;
					for(int x1 = 0; x1 < 2; x1++){
						for(int x2 = 0; x2 < 2; x2++) {
							int x3 = 1 ^ x1 ^ b1;
							
							if(x3 ^ x2 ^ b2) {
								ans += (ll)choose(p[0][l] + p[2][l] - dp[l][r],x1)% mod * choose(p[1][r] + p[2][r] - dp[l][r],x2) % mod * choose(dp[l][r],x3)% mod * P %mod; 
								ans %= mod;
							}
						}
					}
				}
			}	
		}
	}
	cout << ans;
 }

Compilation message (stderr)

xorsum.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main(){
      | ^~~~

• 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