fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define all(x) begin(x),end(x)
  4. typedef long long ll;
  5. typedef vector<int> vi;
  6. typedef vector<vi> vvi;
  7. typedef pair<int,int> pi;
  8. const int mxN = 1e5+1, oo = 1e9;
  9. template<typename T> struct fenwick {
  10.     int n;
  11.     vector<T> fen;
  12.     fenwick(){}
  13.     fenwick(int nn) {
  14.         fen.resize(nn+1);
  15.         n = nn;
  16.     }
  17.     auto sum(int i) {
  18.         T ans = 0;
  19.         while(i) {
  20.             ans+=fen[i];
  21.             i&=i-1;
  22.         }
  23.         return ans;
  24.     }
  25.     auto query(int l, int r) {
  26.         return sum(r+1)-sum(l);
  27.     }
  28.     void update(int i, T val) {
  29.         ++i;
  30.         while(i<=n) {
  31.             fen[i]+=val;
  32.             i+= i&(-i);
  33.         }
  34.     }
  35. };
  36. int main() {
  37.     ios_base::sync_with_stdio(false);
  38.     cin.tie(NULL);
  39.     int n; cin >> n;
  40.     vi sec(n,-1);
  41.     vi a(2*n); 
  42.     for(int i=0;i<2*n;++i) {
  43.         cin >> a[i],a[i]--;
  44.         if(sec[a[i]]==-1) sec[a[i]]=i;
  45.     }
  46.     ll ans = n;
  47.     fenwick<int> fen(2*n);
  48.     for(int i=0;i<2*n;++i) {
  49.         auto couple = sec[a[i]];
  50.         if(couple==i) continue;
  51.         ans+= i-couple-1-fen.query(couple+1,i-1);
  52.         fen.update(couple,1);
  53.         fen.update(i,1);
  54.     }
  55.     cout << ans << '\n';
  56. }
Success #stdin #stdout 0.01s 5496KB
comments (?)
stdin
copy 
5
5 1 2 3 2 3 1 4 5 4
stdout
copy 
7
https://ideone.com/K0MOwM
language:
C++14 (gcc 8.3)
created:
2 years 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!