hiho week 39 register

Ended

Participants:2159

Verdict:Accepted
Score:100 / 100
Submitted:2015-04-01 21:50:00

Lang:G++

Edit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
using namespace std;
int num[100000], buffer[100000];
int n;
long long MergeSort(int a[], int temp[], int size)
{
    if(size == 1)
        return 0;
    long long inverse_count = MergeSort(a, temp, size / 2);
    inverse_count += MergeSort(a + size / 2, temp, size - size / 2);
    for(int left_index = 0, right_index = size / 2; left_index < size / 2; ++left_index)
    {
        while(right_index < size && a[right_index] < a[left_index])
            ++right_index;
        inverse_count += right_index - size / 2;
    }
    
    for(int i = 0; i < size / 2; ++i)
        temp[i] = a[i];
    for(int i = size / 2; i < size; ++i)
        temp[i] = a[size - 1 + size / 2 - i];
    
    for(int i = 0, left = 0, right = size - 1; i < size; ++i)
    {
        if(temp[left] <= temp[right])
            a[i] = temp[left++];
        else
            a[i] = temp[right--];
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX