vikalp14's blog

By vikalp14, 2 months ago, In English,
#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?

 
 
 
 
  • Vote: I like it  
  • +9
  • Vote: I do not like it  

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vikalp14 (previous revision, new revision, compare).

»
2 months ago, # |
Rev. 6   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    don't you dislike when people do #define ll int

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      He updated the code, I think it was written #define ll long long in the first version, but still it works in both cases, I tested it too. However defining "ll" as "int" is really pointless, first time seeing that.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I wonder who are those "great" people who just randomly downvote every comment. Looks like they have nothing better to do in their lives...

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    https://hack.codingblocks.com/contests/c/452/270 This is the problem link. This is where I am still getting error