Untitled

mail@pastecode.io avatar
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;
}