Submission #354335

#	Time	Username	Problem	Language	Result	Execution time	Memory
354335		cheissmart	Intergalactic ship (IZhO19_xorsum)	C++14	0 / 100	787 ms	193260 KiB

xorsum

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
 
const int INF = 1e9 + 9, N = 1003, M = 1e9 + 7, K = 7;
 
int a[N], pw[100005];
int cnt[N][N][K][K], cc[N][K];
// 0 -> 0 1
// 1 -> 1 0
// 2 -> 1 1
 
void add(int& a, int b) {
	a += b;
	if(a >= M) a -= M;
}
 
signed main()
{
	IO_OP;
 
	pw[0] = 1;
	for(int i = 1; i < 100005; i++)
		pw[i] = pw[i - 1] * 2 % M;
 
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	int q;
	cin >> q;
	for(int i = 0; i < q; i++) {
		int l, r, x;
		cin >> l >> r >> x;
		for(int bit1 = 0; bit1 < K; bit1++) {
			if(x >> bit1 & 1) {
				cc[l][bit1]++;
				cc[r + 1][bit1]--;
			}
			for(int bit2 = 0; bit2 < K; bit2++) {
				int t1 = x >> bit1 & 1, t2 = x >> bit2 & 1;
				if(t1 == 0 || t2 == 0) continue;
				cnt[l][l][bit1][bit2]++;
				cnt[l][r + 1][bit1][bit2]--;
				cnt[r + 1][l][bit1][bit2]--;
				cnt[r + 1][r + 1][bit1][bit2]++;
			} 
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < K; j++)
			cc[i][j] += cc[i - 1][j];
	}
	// TODO: change for loop order and see time
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			for(int bit1 = 0; bit1 < K; bit1++) {
				for(int bit2 = 0; bit2 < K; bit2++) {
					cnt[i][j][bit1][bit2] += cnt[i - 1][j][bit1][bit2] +
					 						 cnt[i][j - 1][bit1][bit2] -
					 						 cnt[i - 1][j - 1][bit1][bit2];
				}
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = i; j <= n; j++) {
			int occ = i * (n - j + 1);
			for(int bit1 = 0; bit1 < K; bit1++) {
				for(int bit2 = 0; bit2 < K; bit2++) {
					int mul = (ll(occ) << (bit1 + bit2)) % M;
					if(i < j) mul = mul * 2 % M;
					int c11 = cnt[i][j][bit1][bit2];
					int c10 = cc[i][bit1] - c11;
					int c01 = cc[j][bit2] - c11;
					int c00 = q - c01 - c10 - c11;
					int tt = 0;
					int ways00 = 1, ways11 = 1;
					int t1 = a[i] >> bit1 & 1, t2 = a[j] >> bit2 & 1;
					if(t1 == 0 && t2 == 0) {
						if(c01) ways00 = (ll) ways00 * pw[c01 - 1] % M;
						if(c10) ways00 = (ll) ways00 * pw[c10 - 1] % M;
 
						if(c01 == 0 || c10 == 0) ways11 = 0;
						else {
							ways11 = (ll) ways11 * pw[c01 - 1] % M;
							ways11 = (ll) ways11 * pw[c10 - 1] % M;
						}
					} else if(t1 == 1 && t2 == 1) {
						if(c01) ways11 = (ll) ways11 * pw[c01 - 1] % M;
						if(c10) ways11 = (ll) ways11 * pw[c10 - 1] % M;
 
						if(c01 == 0 || c10 == 0) ways00 = 0;
						else {
							ways00 = (ll) ways00 * pw[c01 - 1] % M;
							ways00 = (ll) ways00 * pw[c10 - 1] % M;
						}
					} else if(t1 == 1 && t2 == 0) {
						if(c01) ways00 = (ll) ways00 * pw[c01 - 1] % M;
 
						if(c10) ways00 = (ll) ways00 * pw[c10 - 1] % M;
						else ways00 = 0;
 
						if(c01) ways11 = (ll) ways11 * pw[c01 - 1] % M;
						else ways11 = 0;
 
						if(c10) ways11 = (ll) ways11 * pw[c10 - 1] % M;
					} else if(t1 == 0 && t2 == 1) {
						if(c01) ways00 = (ll) ways00 * pw[c01 - 1] % M;
						else ways00 = 0;
 
						if(c10) ways00 = (ll) ways00 * pw[c10 - 1] % M;
 
						if(c01) ways11 = (ll) ways11 * pw[c01 - 1] % M;
						
						if(c10) ways11 = (ll) ways11 * pw[c10 - 1] % M;
						else ways11 = 0;
					} else throw;
					if(c00) add(tt, (ll) ways11 * pw[c00 - 1] % M);
					else add(tt, ways11);
					if(c11) add(tt, (ll) ways00 * pw[c11 - 1] % M);
					tt = (ll) tt * pw[c00] % M;
					add(ans, (ll) tt * mul % M);
				}
			}
		}
	}
	cout << ans << endl;
 
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9
• Subtask 5: 0 / 8
• Subtask 6: 0 / 11
• Subtask 7: 0 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8