Advertisement
CooBin

camel

Jul 17th, 2018
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int N = 200000 + 10;
  8.  
  9. void read(ll &x){
  10.     char c;
  11.     do { c = getchar(); } while (!isdigit(c));
  12.     x = c - '0';
  13.     while (isdigit(c = getchar())) x = x * 10 + c - '0';
  14. }
  15.  
  16. ll n;
  17. int pos[N][4];
  18. vector<pair<int, int > > V;
  19. int val[N];
  20.  
  21. int get(int x){
  22.     int ans = 0;
  23.     for (; x > 0; x -= x & -x) ans += val[x];
  24.     return ans;
  25. }
  26.  
  27. void add(int x){ for (; x <= n; x += x & -x) val[x] ++; }
  28.  
  29. ll get(int id1, int id2){
  30.     memset(val, 0, sizeof val);
  31.     V.clear();
  32.     for (int i = 1; i <= n; ++i)
  33.         V.push_back({pos[i][id1], pos[i][id2]});
  34.     sort(V.begin(), V.end());
  35.  
  36.     ll ans = 0;
  37.     for (int i = 0; i < n; ++i){
  38.         ans += 1LL * get(V[i].second);
  39.         add(V[i].second);
  40.     }
  41.     return ans;
  42. }
  43.  
  44. main(){
  45.     read(n);
  46.     for (int x = 1; x <= 3; ++x)
  47.         for (int i = 1; i <= n; ++i){
  48.             ll va; read(va);
  49.             pos[va][x] = i;
  50.         }
  51.  
  52.     long long ans = get(1, 2) + get(2, 3) + get(1, 3);
  53.     ans -= n * (n - 1) / 2;
  54.     ans /= 2;
  55.     cout << ans << '\n';
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement