#include using namespace std; #pragma region atcoder /*#include using namespace atcoder;*/ //using mint = modint998244353; //using mint = modint1000000007; #pragma endregion #pragma region macros using ll = long long; using pii = pair; using pll = pair; using vi = vector; using vs = vector; using vl = vector; using vb = vector; using vvi = vector>; using vvl = vector>; #define rep(i, n) for(int i = 0; i < n; i++) #define REP(i, a, b) for(int i = a; i < b; i++) #define rrep(i, n) for(int i = n - 1; i >= 0; i--) #define RREP(i, a, b) for(int i = b - 1; i >= a; i--) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((int)(x).size()) #define pb push_back #define lb lower_bound #define ub upper_bound #define fi first #define se second #pragma endregion #pragma region debug for var, v, vv #define debug(var) do{std::cout << #var << " : ";view(var);}while(0) template void view(T e){std::cout << e << std::endl;} template void view(const std::vector& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;} template void view(const std::vector >& vv){cout << endl;int cnt = 0;for(const auto& v : vv){cout << cnt << "th : "; view(v); cnt++;} cout << endl;} #pragma endregion #pragma region int128 std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } #pragma endregion const ll mod = 1000000007; const int inf = 1001001001; const ll INF = 1001001001001001001; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; templatebool chmax(T &a, const T b) { if (abool chmin(T &a, const T b) { if (b0&&a%b); } // 20 / 3 == 7 ll rddiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // -20 / 3 == -7 ll power(ll a, ll p){ll ret = 1; while(p){if(p & 1){ret = ret * a;} a = a * a; p >>= 1;} return ret;} ll modpow(ll a, ll p){ll ret = 1; while(p){if(p & 1){ret = ret * a % mod;} a = a * a % mod; p >>= 1;} return ret;} /*--------------------------------------------------------------------------------------------------------------------------------*/ // 0-indexed template struct BIT{ vector data; vector> data2; int _n, _n1, _n2, cnt; BIT(int n) : _n(n), data(n) { cnt = 1; while(cnt < n) cnt *= 2; }; BIT(int n1, int n2) : _n1(n1), _n2(n2) { data2.resize(_n1); for(int i = 0; i < n1; i++) data2[i].resize(_n2, 0); }; void add(int p, T x = 1){ assert(0 <= p && p < _n); p++; while(p <= _n){ data[p - 1] += x; p += p & -p; } } //[l, r) T sum(int l, int r){ assert(0 <= l && l <= r && r <= _n); return sum(r) - sum(l); } //[0, r) T sum(int r){ T sum = 0; while(r > 0){ sum += data[r - 1]; r -= r & -r; } return sum; } //V0 + V1 + ... + Vpos >= val の posを返す int lower_bound(T val){ if(val <= 0) return 0; int pos = 0; for(int k = cnt; k > 0; k /= 2){ if(pos + k <= _n && data[pos + k - 1] < val){ val -= data[pos + k - 1]; pos += k; } } return pos; } void add_2D(int x, int y, T val){ assert(0 <= x && x < _n1 && 0 <= y && y < _n2); x++, y++; for(int i = x; i <= _n1; i++){ for(int j = y; j <= _n2; j++){ data2[x - 1][y - 1] += val; } } } //[0, x][0, y] T sum_2D(int x, int y){ assert(0 <= x && x < _n1 && 0 <= y && y < _n2); T sum = 0; x++, y++; for(int i = x; i >= 0; i -= i & -i){ for(int j = y; j >= 0; j -= j & -j){ sum += data2[i][j]; } } return sum; } }; /** * Coordinate Compresison * O(nlogn) complexity * In this function, X will be replaced by the compressed vector starting from 0 * you can get the original element using vector vals **/ template vector compress(vector &X){ vector vals = X; // sort vals sort(vals.begin(), vals.end()); // delete the adjacent repeating number and remove the garbage in the back. vals.erase(unique(vals.begin(), vals.end()), vals.end()); // do binary search for each element and ask for the position of it for(int i = 0; i < X.size(); i++){ X[i] = lower_bound(vals.begin(), vals.end(), X[i]) - vals.begin(); } return vals; } int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); int n; cin >> n; BIT bit(2*n); vl a(n), b(n); rep(i,n) cin >> a[i]; rep(i,n) cin >> b[i]; vl tmp(2*n); rep(i,n) tmp[i] = a[i]; REP(i,n,2*n) tmp[i] = b[i - n]; compress(tmp); rep(i,n) a[i] = tmp[i]; sort(all(a)); ll ans = 0; for(int i = 0; i < n; i++){ bit.add(tmp[i + n], 1); ans += bit.sum(a[i]); } cout << ans << endl; } /* * review you code when you get WA (typo? index?) * int overflow, array bounds * special cases (n=1?) */