Untitled
unknown
c_cpp
3 years ago
2.3 kB
2
Indexable
Never
/// adil sultanov | vonat1us #pragma GCC optimize("O3") //#pragma comment(linker, "/STACK:36777216") #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define sz(x) (int) x.size() #define all(z) (z).begin(), (z).end() using namespace std; using ll = long long; using pii = pair<int, int>; const int MOD = 1e9 + 7; const int INF = 1e9 + 1e2; void fin() { #ifdef AM freopen(".in", "r", stdin); #endif } const bool flag = 0; const int N = 1e5+10; int aa[2][2][2][18][1<<18], BB[2][2][2][18][1<<18]; vector<int> v[1<<18]; void ma1n() { int n; cin >> n; vector<int> a(n); for (int& x : a) cin >> x; vector<int> b(n); for (int& x : b) cin >> x; ll ans = 0; vector<int> c(n); for (int bt = 17; bt >= 0; --bt) { for (int i = 0; i < n; ++i) { int xr = (a[i]^b[i]); if (xr>>(bt+1)&1) c[i] |= (1<<(bt+1)); int ba = (a[i]>>bt&1); int bb = (b[i]>>bt&1); for (int j = 0; j < 18; ++j) { ans += (1ll<<j) * aa[~a[i]>>j&1][ba][!bb][j][c[i]]; ans += (1ll<<j) * BB[~b[i]>>j&1][!ba][bb][j][c[i]]; aa[a[i]>>j&1][ba][bb][j][c[i]]++; BB[b[i]>>j&1][ba][bb][j][c[i]]++; } } /// del: for (int i = 0; i < n; ++i) { int ba = (a[i]>>bt&1); int bb = (b[i]>>bt&1); for (int j = 0; j < 18; ++j) { aa[a[i]>>j&1][ba][bb][j][c[i]]--; BB[b[i]>>j&1][ba][bb][j][c[i]]--; } } } for (int i = 0; i < n; ++i) { v[a[i]^b[i]].pb(i); } for (int x = 0; x < (1<<18); ++x) { if (sz(v[x]) == 1) continue; for (int j = 0; j < 18; ++j) { int cnt[] = {0, 0}; for (int i : v[x]) { cnt[a[i]>>j&1]++; } ans += (1ll<<j) * cnt[0] * cnt[1]; } } cout << ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr), fin(); int ts = 1; if (flag) { cin >> ts; } while (ts--) { ma1n(); } return 0; }