Submission #876589

#TimeUsernameProblemLanguageResultExecution timeMemory
876589vjudge1Intergalactic ship (IZhO19_xorsum)C++17
100 / 100
1794 ms14920 KiB
// 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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...