Submission #1458766

---

Source Code Expand

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

long long inv(int* a, int cnt) {
  if (cnt <= 1) return 0;
  long long res = inv(a, cnt/2) + inv(a + cnt/2, cnt-cnt/2);
  sort(a, a+cnt/2);
  sort(a+cnt/2, a+cnt);
  int cc = 0;
  for (int i=0; i<cnt/2; i++) {
    while (cc < cnt-cnt/2 && a[cnt/2+cc] < a[i]) cc ++;
    res += cc;
  }
  return res;
}


int a[1000000];

int main()
{
  int n;
  cin >> n;
  for (int i=0; i<n; i++) cin >> a[i];
  cout << inv(a, n) << endl;
}

Submission Info

Judge Result