Submission #257358

#TimeUsernameProblemLanguageResultExecution timeMemory
257358BTheroIntergalactic ship (IZhO19_xorsum)C++17
83 / 100
2080 ms16512 KiB
// chrono::system_clock::now().time_since_epoch().count() #include<bits/stdc++.h> #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define all(x) (x).begin(), (x).end() #define debug(x) cerr << #x << " = " << x << endl; using namespace std; typedef long long ll; typedef pair<int, int> pii; const int MAXN = (int)1e3 + 5; const int MAXQ = (int)1e5 + 5; const int MOD = (int)1e9 + 7; int seg[4][MAXN][MAXN]; array<int, 3> que[MAXQ]; int pw[MAXQ]; int arr[MAXN]; int n, q, ans; int addMod(int a, int b, int m = MOD) { a += b; if (m <= a) { a -= m; } return a; } int mulMod(int a, int b, int m = MOD) { return a * 1ll * b % m; } int binPow(int a, int b, int m = MOD) { int ret = 1; while (b > 0) { if (b & 1) { ret = mulMod(ret, a, m); } a = mulMod(a, a, m); b >>= 1; } return ret; } int bit(int x, int p) { return (x >> p) & 1; } void pre() { pw[0] = 1; for (int i = 1; i < MAXQ; ++i) { pw[i] = mulMod(pw[i - 1], 2); } } int calc(int p1, int p2) { int ret = 0; for (int i = 0; i < 4; ++i) { for (int l = 1; l <= n; ++l) { for (int r = 1; r <= n; ++r) { seg[i][l][r] = 0; } } } for (int i = 1; i <= q; ++i) { auto &[l, r, x] = que[i]; int msk = bit(x, p1) + (bit(x, p2) << 1); seg[msk][l][r]++; } for (int i = 0; i < 4; ++i) { for (int l = 1; l <= n; ++l) { int cur = 0; for (int r = n; r; --r) { cur += seg[i][l][r]; seg[i][l][r] = seg[i][l - 1][r] + cur; } } } for (int a = 1; a <= n; ++a) { for (int b = 1; b <= n; ++b) { array<int, 4> cnt = {0, 0, 0, 0}; int bitA = bit(arr[a], p1); int bitB = bit(arr[b], p2); for (int msk = 0; msk < 4; ++msk) { if (msk == 0) { cnt[0] += seg[msk][n][1]; continue; } array<int, 4> cur; cur[0] = seg[msk][n][1]; cur[1] = seg[msk][a][a]; cur[2] = seg[msk][b][b]; cur[3] = seg[msk][min(a, b)][max(a, b)]; cur[1] -= cur[3]; cur[2] -= cur[3]; cur[0] -= cur[1]; cur[0] -= cur[2]; cur[0] -= cur[3]; for (int msk2 = 0; msk2 < 4; ++msk2) { cnt[(msk & msk2)] += cur[msk2]; } } int cur = 0; for (int x = 0; x < 2; ++x) { if (x > cnt[1]) { continue; } for (int y = 0; y < 2; ++y) { if (y > cnt[2]) { continue; } for (int z = 0; z < 2; ++z) { if (z > cnt[3]) { continue; } if ((bitA ^ x ^ z) == 1 && (bitB ^ y ^ z) == 1) { ++cur; } } } } for (int i = 1; i < 4; ++i) { cur = mulMod(cur, pw[max(0, cnt[i] - 1)]); } cur = mulMod(cur, pw[cnt[0]]); cur = mulMod(cur, mulMod(min(a, b), n - max(a, b) + 1)); ret = addMod(ret, cur); } } return ret; } void solve() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &arr[i]); } scanf("%d", &q); for (int i = 1; i <= q; ++i) { int l, r, x; scanf("%d %d %d", &l, &r, &x); que[i] = {l, r, x}; } for (int a = 0; a < 7; ++a) { for (int b = a; b < 7; ++b) { int cur = mulMod(calc(a, b), (1 << (a + b))); if (b != a) { cur = addMod(cur, cur); } ans = addMod(ans, cur); } } printf("%d\n", ans); } int main() { int tt = 1; pre(); while (tt--) { solve(); } return 0; }

Compilation message (stderr)

xorsum.cpp: In function 'void solve()':
xorsum.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
xorsum.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &arr[i]);
     ~~~~~^~~~~~~~~~~~~~~
xorsum.cpp:168:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
xorsum.cpp:172:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &l, &r, &x);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...