OJ Board

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
static long long sw,n;
static long long v[500001];
void gabung(int p,int q,int r)
{
    long long n1 = q-p+1;
    long long n2 = r-q;
    long long i,j;
    long long L[n1+1], R[n2+1];
    for (i=0;i<n1;i++)
        L[i]=v[p+i];
    for (j=0;j<n2;j++)
        R[j]=v[q+j+1];
    i=0;j=0;
    L[n1]=1000000000;
    R[n2]=1000000000;
    for (int k=p;k<=r;k++)
    {
        if (L[i]<=R[j])
        {
            v[k]=L[i];
            i++;
        }
        else
        {
            v[k]=R[j];
            j++;
            if (L[i]!=1000000000)
                sw+=j;
        }
    }
}
void divide(int awal, int akhir)
{
    if (awal < akhir)
    {
        long long q=(awal+akhir)/2;
        divide(awal,q);
        divide(q+1,akhir);
        gabung(awal,q,akhir);
    }
}
int main()
{
    int temp;
    
    while (cin>>n)
    {
        if (n==0)
            break;
        sw=0;
        memset(v,0,sizeof(v));
        for (int i=0;i<n;i++)
        {
            scanf("%lld",&v[i]);
        }
        divide(0,n-1);
        cout<<sw<<endl;
        //for (int i=0;i<n;i++)
        //    cout<<v[i]<<" ";
        //cout<<endl;
    }
    return 0;
}

Code: Select all

10
324 123 123 123 213 435 678 234 879 234
0

Code: Select all

AC