// https://oj.uz/problem/view/IZhO19_xorsum
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
const int MOD = 1e9 + 7;
int n;
cin >> n;
vector<int> A(n);
for (int i = 0; i < n; i++) cin >> A[i];
int q;
cin >> q;
vector<int> l(q), r(q), x(q);
for (int i = 0; i < q; i++) cin >> l[i] >> r[i] >> x[i], l[i]--;
int64_t p = 1;
int64_t res = 0;
for (int i = 0; i < q; i++) (p *= 2) %= MOD;
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
vector<vector<int>> cntl(n + 1, vector<int>(n + 1));
vector<vector<int>> cntr(n + 1, vector<int>(n + 1));
vector<vector<int>> cntb(n + 1, vector<int>(n + 1));
for (int z = 0; z < q; z++) {
int a = x[z] >> i & 1, b = x[z] >> j & 1;
if (a && b) {
cntb[l[z]][l[z]]++;
cntb[l[z]][r[z]]--;
cntb[r[z]][l[z]]--;
cntb[r[z]][r[z]]++;
cntl[l[z]][r[z]]++;
cntl[l[z]][n]--;
cntl[r[z]][r[z]]--;
cntl[r[z]][n]--;
cntr[0][l[z]]++;
cntr[0][r[z]]--;
cntr[l[z]][l[z]]--;
cntr[l[z]][r[z]]++;
} else if (a) {
cntl[l[z]][0]++;
cntl[l[z]][n]--;
cntl[r[z]][0]--;
cntl[r[z]][n]++;
} else if (b) {
cntr[0][l[z]]++;
cntr[0][r[z]]--;
cntr[n][l[z]]--;
cntr[n][r[z]]++;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j < n; j++) {
cntl[i][j + 1] += cntl[i][j];
cntr[i][j + 1] += cntr[i][j];
cntb[i][j + 1] += cntb[i][j];
}
}
for (int j = 0; j <= n; j++) {
for (int i = 0; i < n; i++) {
cntl[i + 1][j] += cntl[i][j];
cntr[i + 1][j] += cntr[i][j];
cntb[i + 1][j] += cntb[i][j];
}
}
auto prod = [&](int a, int b) -> int64_t {
if (a == 0 && b == 1) return 0;
if (a == 0 && b == 0) return 2;
return 1;
};
for (int x = 0; x < n; x++) {
for (int y = x; y < n; y++) {
int64_t add = (1ll << (i + j)) * (x + 1) * (n - y) * (1 + (x != y));
add %= MOD;
int a = A[x] >> i & 1;
int b = A[y] >> j & 1;
for (int z = 0; z < 8; z++) {
if (((a ^ z ^ (z >> 1)) & 1) && ((b ^ z ^ (z >> 2)) & 1)) {
res += add * p % MOD * prod(cntb[x][y], z & 1) * prod(cntl[x][y], z >> 1 & 1) * prod(cntr[x][y], z >> 2 & 1);
res %= MOD;
}
}
}
}
}
}
res *= MOD + 1 >> 1;
res %= MOD;
res *= MOD + 1 >> 1;
res %= MOD;
res *= MOD + 1 >> 1;
res %= MOD;
cout << res;
}
Compilation message
xorsum.cpp: In function 'int32_t main()':
xorsum.cpp:90:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
90 | res *= MOD + 1 >> 1;
| ~~~~^~~
xorsum.cpp:92:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | res *= MOD + 1 >> 1;
| ~~~~^~~
xorsum.cpp:94:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | res *= MOD + 1 >> 1;
| ~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
8 ms |
348 KB |
Output is correct |
7 |
Correct |
8 ms |
348 KB |
Output is correct |
8 |
Correct |
8 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
2396 KB |
Output is correct |
2 |
Correct |
13 ms |
604 KB |
Output is correct |
3 |
Correct |
8 ms |
460 KB |
Output is correct |
4 |
Correct |
10 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1681 ms |
12420 KB |
Output is correct |
2 |
Correct |
1690 ms |
12392 KB |
Output is correct |
3 |
Correct |
1665 ms |
12484 KB |
Output is correct |
4 |
Correct |
1615 ms |
12632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
472 KB |
Output is correct |
4 |
Correct |
4 ms |
348 KB |
Output is correct |
5 |
Correct |
4 ms |
348 KB |
Output is correct |
6 |
Correct |
4 ms |
348 KB |
Output is correct |
7 |
Correct |
4 ms |
552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
8 ms |
348 KB |
Output is correct |
7 |
Correct |
8 ms |
348 KB |
Output is correct |
8 |
Correct |
8 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
472 KB |
Output is correct |
12 |
Correct |
8 ms |
604 KB |
Output is correct |
13 |
Correct |
8 ms |
348 KB |
Output is correct |
14 |
Correct |
9 ms |
348 KB |
Output is correct |
15 |
Correct |
8 ms |
456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
8 ms |
348 KB |
Output is correct |
7 |
Correct |
8 ms |
348 KB |
Output is correct |
8 |
Correct |
8 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
472 KB |
Output is correct |
12 |
Correct |
4 ms |
348 KB |
Output is correct |
13 |
Correct |
4 ms |
348 KB |
Output is correct |
14 |
Correct |
4 ms |
348 KB |
Output is correct |
15 |
Correct |
4 ms |
552 KB |
Output is correct |
16 |
Correct |
8 ms |
604 KB |
Output is correct |
17 |
Correct |
8 ms |
348 KB |
Output is correct |
18 |
Correct |
9 ms |
348 KB |
Output is correct |
19 |
Correct |
8 ms |
456 KB |
Output is correct |
20 |
Correct |
315 ms |
5688 KB |
Output is correct |
21 |
Correct |
299 ms |
5760 KB |
Output is correct |
22 |
Correct |
265 ms |
5608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
8 ms |
348 KB |
Output is correct |
7 |
Correct |
8 ms |
348 KB |
Output is correct |
8 |
Correct |
8 ms |
348 KB |
Output is correct |
9 |
Correct |
60 ms |
2396 KB |
Output is correct |
10 |
Correct |
13 ms |
604 KB |
Output is correct |
11 |
Correct |
8 ms |
460 KB |
Output is correct |
12 |
Correct |
10 ms |
344 KB |
Output is correct |
13 |
Correct |
1681 ms |
12420 KB |
Output is correct |
14 |
Correct |
1690 ms |
12392 KB |
Output is correct |
15 |
Correct |
1665 ms |
12484 KB |
Output is correct |
16 |
Correct |
1615 ms |
12632 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
472 KB |
Output is correct |
20 |
Correct |
4 ms |
348 KB |
Output is correct |
21 |
Correct |
4 ms |
348 KB |
Output is correct |
22 |
Correct |
4 ms |
348 KB |
Output is correct |
23 |
Correct |
4 ms |
552 KB |
Output is correct |
24 |
Correct |
8 ms |
604 KB |
Output is correct |
25 |
Correct |
8 ms |
348 KB |
Output is correct |
26 |
Correct |
9 ms |
348 KB |
Output is correct |
27 |
Correct |
8 ms |
456 KB |
Output is correct |
28 |
Correct |
315 ms |
5688 KB |
Output is correct |
29 |
Correct |
299 ms |
5760 KB |
Output is correct |
30 |
Correct |
265 ms |
5608 KB |
Output is correct |
31 |
Correct |
1794 ms |
14920 KB |
Output is correct |
32 |
Correct |
1750 ms |
14860 KB |
Output is correct |
33 |
Correct |
1721 ms |
14756 KB |
Output is correct |
34 |
Correct |
1735 ms |
14568 KB |
Output is correct |
35 |
Correct |
1715 ms |
14588 KB |
Output is correct |
36 |
Correct |
1736 ms |
14408 KB |
Output is correct |