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
2018-05-21 12:29:34+0900
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
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