OJ Board

I slove this problem using merge sort but still now Wrong answer please give me any idea about this problem

Thanks in advance.

My problem was that I used an array of size 1000000 when I increase it I got Ac! Try this!

HI "Igor9669" now i got Acc
thanks for your help

hi im getting wrong answer.... i cant understand where is the problem...plz check my code

C++

#define max 10000001

long int a[max];
int main ()
{
long int i,n,cnt,t;
// freopen("in.txt","r",stdin);
while(scanf("%ld",&n)==1)
{
cnt=0;
for(i=1;i<=n;i++)
cin>>a;
for(i=1;i<=n;i++)
{
if(a<i)
{
cnt++;
t=a[a];
a[a]=a;
a=t;
i--;
}
}
printf("%ld\n",cnt);
}
return 0;
}

i cant get any idea how i solve this problem using marge sorts plz give me some hints ...
or give me some critical input for which my code does not work...
plz help me....

im getting runtime error can any one help me out ??/

#include<iostream>
#include<stdio.h>
using namespace std;
#define mx 1000001


long int r1[mx];
long int r2[mx];



int main()
{
long int p;
long int i;
long int cnt;
long int x;

while(scanf("%ld",&p)==1)
{
cnt=0;
for(i=1;i<=p;i++)
{
cin>>x;
r1=x;
r2[x]=i;
}

for(i=1;i<=p;i++)
{
if(r2!=i)
{

x=r1;
r2[x]=r2;
r1[r2]=x;
cnt++;
}

}

printf("%ld\n",cnt);

}


return 0;

}

Think of the case like this
Your code invoke the uninitialized memory read error

use long long to avoid wa

thax for ur help. At first i misunderstand the problem..
then i solve using marge sort..
bt i cant think any better way...
how they solve it under one second runtime...
can anyone help me ?

Use simple merge sort. As I did, apply merge sort to count the swaps..

Can anyone give me some criticial test cases ? I keep getting WA

Input:AC output:

Thanks brianfry713.
I finally solved this problem by using merge sort.
I think this problem can also be solved by using segment trees. But I don't know how to do that.

First count the number of inversion in the left child.
Then count the number of inversion in the right child.
But then how do you count the number of inversion that consists of 1 element from the left child and 1 element from the right child ?
Any hint ?

I used merge sort

I am using mergesort for finding inversion index. but don't understand why I am getting TLE. please help
is there any other technique without using mergesort

Change line 82 to:
while(scanf("%lld",&n)==1)