제출 #342344

#제출 시각아이디문제언어결과실행 시간메모리
342344kekwIntergalactic ship (IZhO19_xorsum)C++17
0 / 100
2068 ms16488 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> #define range(i, n) for (int i = 0; i < (n); ++i) #define ar array #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() typedef long long ll; typedef long double ld; using namespace std; //using namespace __gnu_pbds; const ll INF = 1e18 + 5; const int INFi = 1e9; const int maxN = 1e7 + 1500; const int md2 = 998244353; const int md = 1e9 + 7; int add(int a, int b) { if (a + b >= md) return a + b - md; return a + b; } int sub(int a, int b) { if (a - b < 0) return a - b + md; return a - b; } int mul(int a, int b) { return (1ll * a * b) % md; } int binpow(int a, int b) { if (b <= 0) return 1; if (b % 2) return mul(a, binpow(a, b - 1)); int m = binpow(a, b / 2); return mul(m, m); } int rev(int a) { return binpow(a, md - 2); } void solve() { int n; cin >> n; vector<int> a(n); range(i, n) cin >> a[i]; int q; cin >> q; vector<int> st2(q + 5); st2[0] = 1; for (int i = 1; i < st2.size(); ++i) st2[i] = mul(st2[i - 1], 2); vector<ar<int, 3>> b(q); range(i, q) range(j, 3) cin >> b[i][j]; int ans = 0; sort(all(b)); range(b1, 8) { range(b2, 8) { int result = 0; vector<vector<ar<int, 4>>> Cnt(n + 5, vector<ar<int, 4>>(n + 5)); auto ADD = [&](int x1, int y1, int x2, int y2, int m) { Cnt[x1][y1][m] += 1; Cnt[x1][y1][0] -= 1; Cnt[x2 + 1][y2 + 1][m] += 1; Cnt[x2 + 1][y2 + 1][0] -= 1; Cnt[x1][y2 + 1][m] -= 1; Cnt[x2 + 1][y1][m] -= 1; Cnt[x1][y2 + 1][0] += 1; Cnt[x2 + 1][y1][0] += 1; }; range(i, q) { auto[l, r, x] = b[i]; Cnt[0][0][0]++; if ((x & (1 << b1)) && (x & (1 << b2))) { ADD(l - 1, l - 1, r - 1, r - 1, 3); ADD(l - 1, r, r - 1, n, 1); if (l != 1) ADD(0, l - 1, l - 2, r - 1, 2); } else if (x & (1 << b1)) { ADD(l - 1, 0, r - 1, n, 1); } else if (x & (1 << b2)) { ADD(0, l - 1, n, r - 1, 2); } } range(i, n) { range(j, n) { range(e, 4) { if (i) Cnt[i][j][e] += Cnt[i - 1][j][e]; if (j) Cnt[i][j][e] += Cnt[i][j - 1][e]; if (i && j) Cnt[i][j][e] += Cnt[i - 1][j - 1][e]; } } } range(i, n) { for (int j = i; j < n; ++j) { auto cnt = Cnt[i][j]; int cur = 0; if (cnt[1] && cnt[2]) { cur = st2[q - 2]; } else if (cnt[1] && cnt[3]) { cur = st2[q - 2]; } else if (cnt[2] && cnt[3]) { cur = st2[q - 2]; } else if (cnt[1]) { if (a[j] & (1 << b2)) { cur = st2[q - 1]; } } else if (cnt[2]) { if (a[i] & (1 << b1)) { cur = st2[q - 1]; } } else if (cnt[3]) { int A = (a[i] >> b1) & 1; int B = (a[j] >> b2) & 1; if (A == B) { cur = st2[q - 1]; } } else if (((a[i] >> b1) & 1) && ((a[j] >> b2) & 1)) { cur = st2[q]; } result = add(result, mul(1 + (i != j), mul(cur, mul(i + 1, n - j)))); } } ans = add(ans, mul(result, 1 << (b1 + b2))); } } cout << ans << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(15) << fixed; int tests = 1; //cin >> tests; range(_, tests) { solve(); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

xorsum.cpp: In function 'void solve()':
xorsum.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 1; i < st2.size(); ++i) st2[i] = mul(st2[i - 1], 2);
      |                     ~~^~~~~~~~~~~~
#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...