Submission #689846

#	Time	Username	Problem	Language	Result	Execution time	Memory
689846		vovamr	Intergalactic ship (IZhO19_xorsum)	C++17	17 / 100	1590 ms	212024 KiB

xorsum

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

constexpr int md = 1e9 + 7; constexpr int iv2 = (md + 1) / 2;
inline int add(int a, const int &b) { if((a+=b)>=md)a-=md; return a; }
inline void adds(int &a, const int &b) { if((a+=b)>=md)a-=md; }
inline int sub(int a, const int &b) { if((a-=b)<0)a+=md; return a; }
inline void subs(int &a, const int &b) { if ((a-=b)<0)a+=md; }
inline int mul(int a, const int &b) { return 1ll*a*b%md; }
inline void muls(int &a, const int &b) { a=(1ll*a*b%md); }
inline int bp(int a, int n) { int res = 1;
	for (; n; n >>= 1, muls(a, a)) {
		if (n & 1) muls(res, a);
	} return res;
}
inline int inv(int a) { return bp(a, md - 2); }

const int N = 1e3 + 100;
const int M = 1e5 + 10;

int pw[M];
inline void pre() {
	pw[0] = 1;
	for (int i = 1; i < M; ++i) {
		pw[i] = mul(pw[i - 1], 2);
	}
}

int a[N];
int cnt[7][N];
int cnt_c[7][7][N][N];

inline int calc(const ve<int> &a) {
	int n = sz(a), ans = 0;
	for (int i = n - 1; ~i; --i) {
		for (int j = i + 1; j < n; ++j) {
			adds(ans, mul(mul(a[i], a[j]), mul(i + 1, n - j)));
		}
	}
	muls(ans, 2);
	for (int i = 0; i < n; ++i) {
		adds(ans, mul(mul(a[i], a[i]), mul(i + 1, n - i)));
	}
	return ans;
}

inline void solve() { pre();
	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 z = 0; z < 7; ++z) {
			if (x >> z & 1 ^ 1) continue;
			++cnt[z][l];
			--cnt[z][r + 1];
		}

		for (int a = 0; a < 7; ++a) {
			for (int b = 0; b < 7; ++b) {
				if ((x >> a & 1) && (x >> b & 1)) {
					++cnt_c[a][b][l][l];
					--cnt_c[a][b][l][r + 1];
					--cnt_c[a][b][r + 1][l];
					++cnt_c[a][b][r + 1][r + 1];
				}
			}
		}
	}

	for (int z = 0; z < 7; ++z) {
		for (int i = 1; i <= n; ++i) {
			cnt[z][i] += cnt[z][i - 1];
		}
	}
	for (int a = 0; a < 7; ++a) {
		for (int b = 0; b < 7; ++b) {
			for (int i = 1; i <= n; ++i) {
				for (int j = 1; j <= n; ++j) {
					cnt_c[a][b][i][j] += cnt_c[a][b][i - 1][j];
					cnt_c[a][b][i][j] += cnt_c[a][b][i][j - 1];
					cnt_c[a][b][i][j] -= cnt_c[a][b][i - 1][j - 1];
				}
			}
		}
	}

	auto C = [&](int n, int k) {
		int res = 1;
		for (int i = 2; i <= n; ++i) res *= i;
		for (int i = 1; i <= k; ++i) res /= i;
		for (int i = 1; i <= n - k; ++i) res /= i;
		return res;
	};

	int ans = 0;

	for (int i = 1; i <= n; ++i) {
		for (int bi = 0; bi < 7; ++bi) {

			int ci = a[i] >> bi & 1;

			for (int j = i + 1; j <= n; ++j) {
				for (int bj = 0; bj < 7; ++bj) {

					int cj = a[j] >> bj & 1;

					int cnt_a = cnt[bi][i];
					int cnt_b = cnt[bj][j];
					int cnt_common = cnt_c[bi][bj][i][j];
					int left = q - (cnt_a + cnt_b - cnt_common);

					cnt_a -= cnt_common;
					cnt_b -= cnt_common;

					for (auto [p1, w1] : {pii{0, !cnt_a ? 1 : pw[cnt_a - 1]}, pii{1, !cnt_a ? 0 : pw[cnt_a - 1]}}) {
					for (auto [p2, w2] : {pii{0, !cnt_b ? 1 : pw[cnt_b - 1]}, pii{1, !cnt_b ? 0 : pw[cnt_b - 1]}}) {
					for (auto [p3, w3] : {pii{0, !cnt_common ? 1 : pw[cnt_common - 1]}, pii{1, !cnt_common ? 0 : pw[cnt_common - 1]}}) {
						if ((ci ^ p1 ^ p3) && (cj ^ p2 ^ p3)) {
							adds(ans, mul(1 << (bi + bj), mul(mul(i, n - j + 1), mul(1 << left, mul(mul(w1, w2), w3)))));
						}
					}}}
				}
			}
		}
	}
	muls(ans, 2);
	for (int i = 1; i <= n; ++i) {
		for (int bi = 0; bi < 7; ++bi) {
			for (int bj = 0; bj < 7; ++bj) {
				int ci = (a[i] >> bi & 1);
				int cj = (a[i] >> bj & 1);

				int cnt_a = cnt[bi][i];
				int cnt_b = cnt[bj][i];
				int cnt_common = cnt_c[bi][bj][i][i];
				int left = q - (cnt_a + cnt_b - cnt_common);

				cnt_a -= cnt_common;
				cnt_b -= cnt_common;

				for (auto [p1, w1] : {pii{0, !cnt_a ? 1 : pw[cnt_a - 1]}, pii{1, !cnt_a ? 0 : pw[cnt_a - 1]}}) {
				for (auto [p2, w2] : {pii{0, !cnt_b ? 1 : pw[cnt_b - 1]}, pii{1, !cnt_b ? 0 : pw[cnt_b - 1]}}) {
				for (auto [p3, w3] : {pii{0, !cnt_common ? 1 : pw[cnt_common - 1]}, pii{1, !cnt_common ? 0 : pw[cnt_common - 1]}}) {
					if ((ci ^ p1 ^ p3) && (cj ^ p2 ^ p3)) {
						adds(ans, mul(1 << (bi + bj), mul(mul(i, n - i + 1), mul(1 << left, mul(mul(w1, w2), w3)))));
					}
				}}}	
			}
		}
	}

	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message (stderr)

xorsum.cpp: In function 'void solve()':
xorsum.cpp:78:15: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   78 |    if (x >> z & 1 ^ 1) continue;
      |        ~~~~~~~^~~
xorsum.cpp:112:7: warning: variable 'C' set but not used [-Wunused-but-set-variable]
  112 |  auto C = [&](int n, int k) {
      |       ^

• 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