Submission #975500

#TimeUsernameProblemLanguageResultExecution timeMemory
975500AliHasanliCryptography (NOI20_crypto)C++17
25 / 100
318 ms34100 KiB
#include<bits/stdc++.h> using namespace std; map<int,int>mp; long long fact[300005]; long long a[300005],b[300005],c[300005],seg[1200005]; long long query(long long n,long long l,long long r,long long ql,long long qr) { if(l>r || ql>qr || r<ql || l>qr)return 0; if(ql<=l && r<=qr)return seg[n]; return query(2*n,l,(l+r)/2,ql,qr)+query(2*n+1,(l+r)/2+1,r,ql,qr); } void update(long long n,long long l,long long r,long long pos) { if(l>r || r<pos || l>pos)return; if(l==r){seg[n]=1;return;} update(2*n,l,(l+r)/2,pos),update(2*n+1,(l+r)/2+1,r,pos); seg[n]=seg[2*n]+seg[2*n+1]; } void fac(long long n) { fact[0]=1; for(long long i=1;i<=300004;i++) fact[i]=(i*fact[i-1])%1000000007; } int main() { fac(300004); long long n; cin>>n; for(long long i=0;i<n;i++) { cin>>a[i]; b[i]=a[i]; } sort(b,b+n); for(long long i=1;i<=n;i++) mp[b[i-1]]=i; long long cavab=1; for(long long i=0;i<n;i++) { //cout<<fact[n-i-1]<<" "<<query(1,1,n,1,mp[a[i]])+1<<endl; long long sira=mp[a[i]]-query(1,1,n,1,mp[a[i]]); cavab+=(fact[n-i-1]*(sira-1))%1000000007; update(1,1,n,mp[a[i]]); } cout<<cavab; return 0; } /* 4!*(1-1)+3!(4-1)+2!(1-1)+1!(2-1)+0!(1-1)+1=18+1+1=20; */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...