oj.uz

Submission #408979

# Submission time Handle Problem Language Result Execution time Memory
408979 2021-05-20T00:34:03 Z 8e7 Intergalactic ship (IZhO19_xorsum) C++14
45 / 100
 755 ms 9412 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);
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;
	
}
int 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 1 ms 1484 KB Output is correct
2 Correct 1 ms 1528 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1528 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 9 ms 1996 KB Output is correct
7 Correct 9 ms 1996 KB Output is correct
8 Correct 9 ms 1992 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 1980 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 750 ms 9368 KB Output is correct
2 Correct 755 ms 9368 KB Output is correct
3 Correct 736 ms 9412 KB Output is correct
4 Correct 725 ms 9412 KB Output is correct

Subtask #5
8.0 / 8.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 2 ms 1612 KB Output is correct
3 Correct 2 ms 1612 KB Output is correct
4 Incorrect 7 ms 1636 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 1 ms 1484 KB Output is correct
2 Correct 1 ms 1528 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 9 ms 1996 KB Output is correct
7 Correct 9 ms 1996 KB Output is correct
8 Correct 9 ms 1992 KB Output is correct
9 Correct 2 ms 1612 KB Output is correct
10 Correct 2 ms 1612 KB Output is correct
11 Correct 2 ms 1612 KB Output is correct
12 Correct 10 ms 2000 KB Output is correct
13 Correct 10 ms 2000 KB Output is correct
14 Correct 9 ms 2000 KB Output is correct
15 Correct 9 ms 1996 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1528 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 9 ms 1996 KB Output is correct
7 Correct 9 ms 1996 KB Output is correct
8 Correct 9 ms 1992 KB Output is correct
9 Correct 2 ms 1612 KB Output is correct
10 Correct 2 ms 1612 KB Output is correct
11 Correct 2 ms 1612 KB Output is correct
12 Incorrect 7 ms 1636 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1528 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 9 ms 1996 KB Output is correct
7 Correct 9 ms 1996 KB Output is correct
8 Correct 9 ms 1992 KB Output is correct
9 Incorrect 102 ms 1980 KB Output isn't correct
10 Halted 0 ms 0 KB -