fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int limN = 2e5 + 5;
  4.  
  5. int n, a[limN], b[limN], pos[limN], v[limN], st[4 * limN];
  6.  
  7. void update(int id, int l, int r, int pos) {
  8.     if (l == r) {
  9.         ++st[id];
  10.         return;
  11.     }
  12.     int mid = (l + r) >> 1;
  13.     if (pos <= mid) update(id << 1, l, mid, pos);
  14.     else update(id << 1 | 1, mid + 1, r, pos);
  15.     st[id] = st[id << 1] + st[id << 1 | 1];
  16. }
  17.  
  18. int query(int id, int l, int r, int u, int v) {
  19.     if (v < l || r < u) return 0;
  20.     if (u <= l && r <= v) return st[id];
  21.     int mid = (l + r) >> 1;
  22.     return query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v);
  23. }
  24.  
  25. int main() {
  26.     ios::sync_with_stdio(false), cin.tie(nullptr);
  27.     cin >> n;
  28.     for (int i = 1; i <= n; ++i) cin >> a[i];
  29.     for (int i = 1; i <= n; ++i)
  30.         cin >> b[i], pos[b[i]] = i;
  31.     for (int i = 1; i <= n; ++i) v[i] = pos[a[i]];
  32.  
  33.     int ans = 0;
  34.     memset(st, 0, sizeof(st));
  35.  
  36.     for (int i = 1; i <= n; ++i) {
  37.         int val = query(1, 1, n, v[i] + 1, n);
  38.         if (val > 0) ++ans;
  39.         update(1, 1, n, v[i]);
  40.     }
  41.  
  42.     cout << ans << '\n';
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0.01s 7408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/AmP05v
language:
C++14 (gcc 8.3)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!