Submission #2543022
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);
T.inc(A[i],inv((D[A[i]])+MOD)%MOD);
}
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:25:53+0900
Task
E - Inversions
User
Demerzel_IV
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2056 Byte
Status
RE
Exec Time
156 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
0 / 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
RE
98 ms
2944 KB
sample_02.txt
RE
99 ms
2944 KB
sample_03.txt
AC
2 ms
2304 KB
sample_04.txt
RE
102 ms
2944 KB
subtask_1_01.txt
RE
99 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
RE
110 ms
3456 KB
subtask_1_06.txt
RE
140 ms
4608 KB
subtask_1_07.txt
RE
113 ms
3584 KB
subtask_1_08.txt
RE
107 ms
3840 KB
subtask_1_09.txt
RE
107 ms
3968 KB
subtask_1_10.txt
RE
104 ms
3328 KB
subtask_1_11.txt
RE
130 ms
4224 KB
subtask_1_12.txt
RE
121 ms
4352 KB
subtask_1_13.txt
RE
120 ms
4736 KB
subtask_1_14.txt
AC
22 ms
3072 KB
subtask_1_15.txt
AC
21 ms
3072 KB
subtask_1_16.txt
RE
155 ms
4992 KB
subtask_1_17.txt
RE
154 ms
4992 KB
subtask_1_18.txt
RE
155 ms
4992 KB
subtask_1_19.txt
RE
126 ms
4992 KB
subtask_1_20.txt
RE
124 ms
4992 KB
subtask_1_21.txt
RE
124 ms
4992 KB
subtask_1_22.txt
RE
151 ms
4992 KB
subtask_1_23.txt
RE
141 ms
4992 KB
subtask_1_24.txt
RE
128 ms
4992 KB
subtask_1_25.txt
AC
22 ms
3072 KB
subtask_1_26.txt
AC
22 ms
3072 KB
subtask_1_27.txt
RE
156 ms
4992 KB
subtask_1_28.txt
RE
153 ms
4992 KB
subtask_1_29.txt
RE
153 ms
4992 KB
subtask_1_30.txt
RE
126 ms
4992 KB
subtask_1_31.txt
RE
124 ms
4992 KB
subtask_1_32.txt
RE
121 ms
4992 KB
subtask_1_33.txt
RE
152 ms
4992 KB
subtask_1_34.txt
RE
142 ms
4992 KB
subtask_1_35.txt
RE
126 ms
4992 KB