Submission #408985

#	Time	Username	Problem	Language	Result	Execution time	Memory
408985		8e7	Intergalactic ship (IZhO19_xorsum)	C++14	100 / 100	901 ms	12408 KiB

xorsum

//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <set>
#define ll long long
#define maxn 1005
#define maxq 100005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define int ll
using namespace std;
int a[maxn];
struct query{
	int l, r, x;
	query(int a, int b, int c) {
		l = a, r = b, x = c;
	}
	query() {
		l = 0, r = 0, x = 0;
	}
} que[maxq];
ll po[maxq];
int n, q;
ll cnt[maxn][maxn], one[2][maxn];
void build2d(int mask) {
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) cnt[i][j] = 0;
	}
	for (int i = 0;i < q;i++) {
		if ((que[i].x & mask) == mask) cnt[que[i].l][que[i].r]++;
	}	
	for (int i = 1;i <= n;i++) {
		for (int j = n;j >= i;j--) cnt[i][j] += cnt[i][j + 1];
		for (int j = n;j >= i;j--) cnt[i][j] += cnt[i - 1][j];
	}
}
void build1d(ll arr[], int mask) {
	for (int i = 0;i <= n;i++) arr[i] = 0;
	for (int i = 0;i < q;i++) {
		if ((que[i].x & mask) == mask) {
			arr[que[i].l]++, arr[que[i].r + 1]--;
		}
	}
	for (int i = 1;i <= n;i++) arr[i] += arr[i - 1];
}
ll ans = 0;
void solve(int b1, int b2) {
	build1d(one[0], b1), build1d(one[1], b2);
	build2d(b1 | b2);
	ll num = (ll)b1 * b2, tmp = 0;
	//cout << b1 << " " << b2 << endl;
	for (int i = 1;i <= n;i++) {
		for (int j = i;j <= n;j++) {
			bool bi = a[i] & b1, bj = a[j] & b2;
			int l = one[0][i], r = one[1][j], both = cnt[i][j];
			l -= both, r -= both;
			ll other = po[q - l - r - both];
			ll pl0 = l == 0 ? 1 : po[l - 1], pl1 = l == 0 ? 0 : po[l - 1];
			ll pr0 = r == 0 ? 1 : po[r - 1], pr1 = r == 0 ? 0 : po[r - 1];
			ll both0 = both == 0 ? 1 : po[both - 1], both1 = both == 0 ? 0 : po[both - 1];
			if (bi) swap(pl0, pl1);
			if (bj) swap(pr0, pr1);
			//cout << i << " " << j << " " << both0 * pl1 * pr1 * i * (n - j + 1) * other << " " << both1 * pl0 * pr0 * i * (n - j + 1) * other << endl;
			//cout << other << endl;
			ll val =  (both0 * pl1 % mod * pr1 % mod + both1 * pl0 % mod * pr0 % mod) % mod * i * (n - j +1) % mod * other % mod;	
			tmp = (tmp + val * (i == j ? 1 : 2) )% mod;
		}
	}	
	ans = (ans + num * tmp) % mod;
	
}
signed main() {
	io
	po[0] = 1;
	for (int i = 1;i < maxq;i++) po[i] = po[i - 1] * 2 % mod;
	cin >>n;
	for (int i = 1;i <= n;i++) cin >> a[i];
	cin >> q;
	for (int i = 0;i < q;i++) {
		cin >> que[i].l >> que[i].r >> que[i].x;	
	}	
	for (int i = 0;i < 7;i++) {
		for (int j = 0;j < 7;j++) {
			solve(1<<i, 1<<j);
		}
	}
	cout << ans << endl;
}
/*
2
1 3
1
1 2 2

5
1 2 3 4 5
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