vikalp14's blog

By vikalp14, 4 years ago,
#include<bits/stdc++.h>
using namespace std;
#define S 100001
#define ll int

ll arr[S];
ll ans;

void merge(int l ,int h , ll (&arr)[S])
{
ll mid=l+(h-l)/2;
long long ar[S];
int i=l;
int j=mid+1;
int k=0;

while(i<=mid && j<=h)
{
if (arr[i]>arr[j])
{
ans+=(mid-i+1);
ar[k++]=arr[j++];
}
else
ar[k++]=arr[i++];
}

while(i<=mid)
ar[k++]=arr[i++];

while (j<=h)
ar[k++]=arr[j++];

for (int i = 0; i < k; ++i)
arr[l++]=ar[i];

}

void merge_sort(int l , int h , ll (&arr)[S])
{

if(l>=h)
return ;

ll m=l+(h-l)/2;

merge_sort(l,m,arr);
merge_sort(m+1,h,arr);
merge(l,h,arr);
}

int main()
{
int t;
cin>>t;

while(t--)
{
ans=0;
int n;
cin>>n;

for(int j=0;j<n;j++)
{
/**************************************comment 1********
/int tp;
/cin>>tp;
/arr[j]=tp;
**********************************************************/

///////////////////////replace following line with comment 1 and you'll get WA
cin>>arr[j];
}

merge_sort(0,n-1,arr);
cout<<ans<<endl;

}
}


Why do I get WA on replacing?

• +9

| Write comment?
 » 4 years ago, # | ← Rev. 6 →   +1 You get WA because array arr is of type long long, and variable tp in main() is of type int. If you declare tp as long long, your solution should be correct.EDIT: I've just tested your code for both types of input and it works. I've also submitted it on this problem by only increasing N to 200001 and declaring ans as long long (which you don't have to do since your N is originally 100001) so it fits into problem's constraints, and it got AC. Screenshot
•  » » 4 years ago, # ^ |   +1 don't you dislike when people do #define ll int