Submission #2543029


Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

typedef long long ll;
const int N=201000,MOD=1000000007;

ll inv(int x){return x==1?1:(-(MOD/x)*inv(MOD%x)%MOD);}

struct bit
{
	int w[N];
	inline void reset(){memset(w,0,sizeof(w));}
	inline int lowbit(int x){return x&(-x);}
	void inc(int p,int x){for(;p<N;p+=lowbit(p))w[p]=(w[p]+x)%MOD;}
	int ask(int p){int ret=0;for(;p;p-=lowbit(p))ret=(ret+w[p])%MOD;return ret;}
}T;

namespace calculator
{
	int cnt[N],D[N],bel[N];
	int *A,n;

	bool judge(int *A_,int n_)
	{
		A=A_,n=n_;
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<n;i++)cnt[i]=-1;
		for(int i=1;i<=n;i++)cnt[A[i]]++;
		for(int i=n;i;i--)cnt[i-1]+=cnt[i];

		for(int i=1;i<=n;i++)if(cnt[i]<1)return 0;
		return 1;
	}
	int solve(int *A_,int n_)
	{
		if(!judge(A_,n_))return 0;

		int ret=0,S=1;
		for(int i=1;i<=n;i++)S=(ll)S*cnt[i]%MOD;

		for(int i=1,j;i<=n;i=j+1)
		{
			for(j=i;j<n && cnt[j+1]!=1;j++);
			for(int k=i;k<=j;k++)bel[k]=i;

			D[i]=1;
			for(int k=i+1;k<=j;k++)
				D[k]=(ll)D[k-1]*(cnt[k]-1)%MOD*inv(cnt[k])%MOD;
		}

		T.reset();

		for(int i=1,x,y,z;i<=n;i++)
		{
			x=A[i]-1,y=bel[A[i]],z=(T.ask(x)-T.ask(y-1))%MOD;

			ret=(ret+(ll)z*D[A[i]]%MOD*S%MOD)%MOD;

			T.inc(A[i],inv(D[A[i]]));
		}

		ret=(ret+MOD)%MOD;

		return ret*inv(2)%MOD;
	}
}

int A[N],cnt[N];
int n,S,ans;

int fuck()
{
	T.reset();
	int ret=0;
	for(int i=1;i<=n;i++)
		ret=(ret+T.ask(n)-T.ask(A[i]))%MOD,T.inc(A[i],1);
	return ret;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",A+i);

	if(!calculator::judge(A,n)){printf("0\n");return 0;}

	for(int i=S=1;i<=n;i++)
		S=(ll)S*calculator::cnt[i]%MOD;

	ans=0;
	for(int i=1;i<=n;i++)
		ans=(ans+cnt[A[i]])%MOD,cnt[A[i]]++;
	ans=(ll)ans*S%MOD*inv(2)%MOD;

	ans=(ans+calculator::solve(A,n))%MOD;

	ans=(ans+(ll)S*fuck())%MOD;
	std::reverse(A+1,A+n+1);
	ans=(ans-calculator::solve(A,n))%MOD;

	ans=(ans+MOD)%MOD;

	printf("%d\n",ans);

	return 0;
}

Submission Info

Submission Time
Task E - Inversions
User Demerzel_IV
Language C++14 (GCC 5.4.1)
Score 1700
Code Size 2050 Byte
Status AC
Exec Time 257 ms
Memory 4992 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:84:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:86:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",A+i);
                  ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1700 / 1700
Status
AC × 4
AC × 43
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 2944 KB
sample_02.txt AC 2 ms 2944 KB
sample_03.txt AC 2 ms 2304 KB
sample_04.txt AC 2 ms 2944 KB
subtask_1_01.txt AC 2 ms 2944 KB
subtask_1_02.txt AC 2 ms 2304 KB
subtask_1_03.txt AC 15 ms 2816 KB
subtask_1_04.txt AC 3 ms 2304 KB
subtask_1_05.txt AC 58 ms 3456 KB
subtask_1_06.txt AC 186 ms 4608 KB
subtask_1_07.txt AC 71 ms 3584 KB
subtask_1_08.txt AC 34 ms 3840 KB
subtask_1_09.txt AC 37 ms 3968 KB
subtask_1_10.txt AC 14 ms 3328 KB
subtask_1_11.txt AC 147 ms 4224 KB
subtask_1_12.txt AC 137 ms 4352 KB
subtask_1_13.txt AC 96 ms 4736 KB
subtask_1_14.txt AC 22 ms 3072 KB
subtask_1_15.txt AC 22 ms 3072 KB
subtask_1_16.txt AC 255 ms 4992 KB
subtask_1_17.txt AC 238 ms 4992 KB
subtask_1_18.txt AC 238 ms 4992 KB
subtask_1_19.txt AC 98 ms 4992 KB
subtask_1_20.txt AC 81 ms 4992 KB
subtask_1_21.txt AC 81 ms 4992 KB
subtask_1_22.txt AC 257 ms 4992 KB
subtask_1_23.txt AC 239 ms 4992 KB
subtask_1_24.txt AC 145 ms 4992 KB
subtask_1_25.txt AC 22 ms 3072 KB
subtask_1_26.txt AC 21 ms 3072 KB
subtask_1_27.txt AC 254 ms 4992 KB
subtask_1_28.txt AC 238 ms 4992 KB
subtask_1_29.txt AC 238 ms 4992 KB
subtask_1_30.txt AC 97 ms 4992 KB
subtask_1_31.txt AC 81 ms 4992 KB
subtask_1_32.txt AC 81 ms 4992 KB
subtask_1_33.txt AC 255 ms 4992 KB
subtask_1_34.txt AC 237 ms 4992 KB
subtask_1_35.txt AC 120 ms 4992 KB