oj.uz

Submission #408982

# Submission time Handle Problem Language Result Execution time Memory
408982 2021-05-20T00:42:42 Z 8e7 Intergalactic ship (IZhO19_xorsum) C++14
45 / 100
 732 ms 10552 KB 
//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 < maxn;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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 10 ms 3176 KB Output is correct
7 Correct 9 ms 3172 KB Output is correct
8 Correct 9 ms 3148 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 3140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 10548 KB Output is correct
2 Correct 732 ms 10548 KB Output is correct
3 Correct 726 ms 10548 KB Output is correct
4 Correct 728 ms 10552 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 3 ms 2764 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 3 ms 2764 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct
4 Incorrect 7 ms 2764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 10 ms 3176 KB Output is correct
7 Correct 9 ms 3172 KB Output is correct
8 Correct 9 ms 3148 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Correct 10 ms 3176 KB Output is correct
13 Correct 10 ms 3148 KB Output is correct
14 Correct 11 ms 3148 KB Output is correct
15 Correct 10 ms 3180 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 10 ms 3176 KB Output is correct
7 Correct 9 ms 3172 KB Output is correct
8 Correct 9 ms 3148 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Incorrect 7 ms 2764 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 10 ms 3176 KB Output is correct
7 Correct 9 ms 3172 KB Output is correct
8 Correct 9 ms 3148 KB Output is correct
9 Incorrect 104 ms 3140 KB Output isn't correct
10 Halted 0 ms 0 KB -