Sgu 180
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <math.h>
#include <limits.h>
 
using namespace std;
 
// Datatypes
typedef vector<int> vi; 
typedef vector<string> vs;
typedef vector<vi> vvi; 
typedef pair<int,int> ii; 
typedef long long ll;
typedef long double ld;
 
// Define
#define sz(a)             int((a).size()) 
#define pb                push_back 
#define all(c)            (c).begin(),(c).end() 
#define present(c,x)      ((c).find(x) != (c).end()) 
#define cpresent(c,x)     (find(all(c),x) != (c).end()) 
#define FOR(_i,_n)        for(int (_i) = 0; (_i) < (_n); (_i)++)
#define mp                make_pair
 
// Constants
const double eps = 1e-8; 
const double PI = 3.1415926535897932384626433832795;
 
#define INPUT_FILE "xo.in"
#define OUTPUT_FILE "xo.out"
 
vector<long long> m;
vector<long long> m1;
vector<long long> m2;
 
long long Merge(int l, int mm, int r)
{
    int n1,n2,i1,i2;
    long long c = 0;
    n1 = n2 = i1 = i2 = 0;
 
    for(int i = l; i <= mm; i++)
    {
        m1[n1] = m[i];
        n1 ++;
    }
    m1[n1] = INT_MAX;
 
    for(int i = mm + 1; i <= r; i++)
    {
        m2[n2] = m[i];
        n2 ++;
    }
    m2[n2] = INT_MAX;
 
    for(int i = l; i <= r; i++)
    {
        if(m1[i1] <= m2[i2])
        {
            m[i] = m1[i1];
            i1++;
        }
        else
        {
            m[i] = m2[i2];
            i2++;
            c += (long long)(n1 - i1);
        }
    }
 
    return c;
}
 
long long MergeSort(int l, int r)
{
    if(r > l)
    {
        int m = (l+r)/2;
        long long a = MergeSort(l, m);
        long long b = MergeSort(m + 1, r);
        long long c = Merge(l,m,r);
        return a + b + c;
    }
    return 0;
}
 
int main(void)
{
#ifdef ALEX
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    //freopen(INPUT_FILE, "r", stdin);
    //freopen(OUTPUT_FILE, "w", stdout);
#endif
 
    int n;
    cin >> n;
    m.resize(n+10);
    m1.resize(n+10);
    m2.resize(n+10);
 
    int t;
    for(int i = 0; i < n; i++)
    {
        cin >> t;
        m[i+1] = t;
    }
 
    cout << MergeSort(1, n) << endl;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.