UVa 11858 - Frosh Week

// UVa 11858 - Frosh Week

#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;

#define integer signed long long

vector<integer> v;

integer merge(integer ini, integer mid, integer fin) {
	vector<integer> a, b;
	for (integer i = ini; i <= mid; i++)
		a.push_back(v[i]);
	for (integer i = mid + 1; i <= fin; i++)
		b.push_back(v[i]);
	integer i = 0;
	integer j = 0;
	integer k = ini;
	integer c = 0;
	while (i < a.size() || j < b.size()) {
		if (i >= a.size())
			v[k++] = b[j++];
		else if (j >= b.size())
			v[k++] = a[i++];
		else if (a[i] <= b[j])
			v[k++] = a[i++];
		else {
			v[k++] = b[j++];
			c += a.size() - i;
		}
	}
	return c;
}

integer mergesort(integer ini, integer fin) {
	if (ini < fin) {
		integer mid = (ini + fin) >> 1;
		integer c = mergesort(ini, mid);
		c += mergesort(mid + 1, fin);
		c += merge(ini, mid, fin);
		return c;
	} else
		return 0;
}

int main() {
	integer n;
	while (cin >> n) {
		v.clear();
		for (integer i = 0; i < n; i++) {
			integer a;
			cin >> a;
			v.push_back(a);
		}
		cout << mergesort(0, n - 1) << endl;
	}
	return 0;
}